Generate a parser code from a grammar to verify a string

Question

I have a grammar, and I want to create a program that take this grammar as a parameter, and generate an output code (in C, Java, Python,...). Therefore, when we compile/run the generated code and pass to it a string/phrase it should check if this string verified with the grammar.

What is the right approach?

Update: Adding the grammar example

S  -> id ':=' E
E  -> T A
A  -> '+' T A | empty
T  -> F B
B  -> '*' F B | empty
F  -> '(' E ')' | id | number

Answer 1

This is not a trivial task and there isn't even one right solution. I recommend you review the lecture notes for the class for which you should prepare the assignment and use a technique that was introduced there.

If your grammar is context free, you can (after converting it into Chomsky normal form) use the Cocke–Younger–Kasami algorithm to check whether it can produce a given word. This algorithm is easy to implement (less than a screen full of Python code) but takes cubic time. It is mostly used in theoretical computer science.

Actual compilers use faster algorithms but they impose additional requirements on the grammar. Check out what was introduced in your lecture. If you want to know how it works in the real world, you can study an existing parser generator like GNU Bison. It is free software so you are free to study its source code.

Good luck!