tags: compiler design, systems
Parsing the input string by tracing out the leftmost derivation* also the parsing tree is traversed from root to the leaves, i.e the root is created first then the nodes, remember just as we used to do before.
Types of top-down parsers
- Backtracking parser
- Predictive parser
A predictive parser tries to predict the next token in the input string. The meaning of “prediction” here is that the parser guesses which grammar rule it should choose based on the token that is next in the input (the look-ahead token).
Recursive descent parsing
A predictive parsing algorithm. The grammar rule is written as a function that will recognize this grammar, the right hand side of the grammar defines the structure of this function, if it is a non terminal, it will call a another function, if they are choices then it will be an if-else statements, if there is repetition then there will be while loop, finally if it is a terminal the next input string must match it.
We can notice that the recursive descent algorithm mirrors EBNF grammar rules in terms of grammar checking, so translating the grammar rules into EBNF is a must to be able to write recursive descent properly.
The token variable in the above code is the look-ahead token. We can see the switch case “predicts” the grammar choice based on the next token that should be matched.
Example
As we can see first exp is parsed then term and term will parse what is beneath it, making it a top down parser that obeys left-most derivation.
Match procedure
Used to match the next token with its parameter, or in other words used to get the look-ahead token. The procedure should report error if the matching is not correct.
Modification on the parser to do other operations
The function above is used to calculate the value of the expression that is parsed. Left associativity is preserved by performing the calculations as the loop is executed and by the recursive in temp = term;, term is a function.
The above is used to construct the syntax tree while parsing.
The above is used to construct the if-stmt syntax tree while parsing.