Given a recursive descent parser, how should I modify it for Syntax Analysis?

Question

I have just finished coding a recursive descent parser for C Minus that simply prints "ACCEPT" if the input text file can be parsed or "REJECT" if not. I have a function for each rule in the grammar that just returns true or false. Here are some of the checks that must be implemented in the syntax analysis:

Basically, my question is, what is the smart way to do this?

I do not have a symbol table right now at all, but I heard classmates say that I can simply put certain checks into the functions themselves. For example, to not allow a float as an array index, just find the function in my code that has the brackets and put some "check" in there to return an error if a float is between two brackets.

Answer 1

Your list of checks are not "syntax" analysis in the sense of grammar checks.

They are "syntax" checks if you interpret only completely valid programs as language instances.

Most of the compiler community would call this "semantic" (validity) checking.

Usually such checks are about whether operators are applied to operands according to the language rules (e.g., "operator [] cannot be used except on array types").

To do this you have to know, for each operator (e.g, "[]") what the type of the operand is. To do that, people typically build symbol tables that map identifiers to the type of the identifier, and map source code regions to sets of identifiers that are valid in those regions ("scopes"). With this information you can check that an operator applied to a symbol make sense.

Now a complication occurs: some operators apply to expressions, e.g., other compositions of operators, e.g,: foo(x)[17] which I intend to mean "foo is a function that is called and returns an array. So now you have to associate type information with every expression.

The easiest way is to associate type information with every node in the tree. You'll need to go read about symbol tables, how to build one by doing a tree walk, and then how to walk the tree labelleling each node with a type (identifiers are easy: the type is what the symobl table says the type of the identifier is). Usually you can do a bottom-up tree walk, labelling leaf nodes first, then check the operator nodes above them for validity, and computing the type of operator node after the validaty check passes, and continuing this process to label tree nodes as your analyzer climbs the tree.

[For some languages, a bottom up scan doesn't work; you have iteratively pass information up and down. Ada is rather famous for this].

A formal characterization of this process is called "attribute evaluation". See https://en.wikipedia.org/wiki/Attribute_grammar. You don't need to be this "formal" to implement the ideas, you can do the bottom up case by hand.

That's the smart way. Other approaches might be possible, but they are hard to imagine and likely hard to make work "right".