javaparsingcompiler-constructioncontext-free-grammarleft-recursion

Creating parse tree to determine correctness of the LL Grammar given


I am have a program that will currently generate a output of tokens that is to be used for a input on this next program. It is going to be checking the correctness of the syntax of the code.

I am running into issues on how I would start converting this grammar to a usable program.

Below is the grammar use, how would I start going about making this. Or where are good resources to help myself learn the basics of creating my own parser.

This implementation is going to be using Java, so if you could have answers corresponding to java's implementation, that would be swell

program → stmt_list $$$

stmt_list → stmt stmt_list | ε

stmt → id = expr | input id | print expr

expr → term term_tail

term_tail → add op term term_tail | ε

term → factor fact_tail

fact_tail → mult_op fact fact_tail | ε

factor → ( expr ) | number | id

add_op → + | -

mult_op → * | / | // | %


Solution

  • You should start by reading the Syntax Analysis chapter of Compilers - Principles, Techniques, and Tools, also known as the dragon book.
    The steps for checking the output tokens are:

  • Build the First and Follow sets.
  • Construct the predictive parsing table.
  • Check for multiple productions in the same table cell(A conflict)

  • All of these steps can be found in the dragon book perfectly explained with their respective algorithms.
    I hope this helps. This is actually just a step before a parse, so if you got to the point of being able to check if the grammar is LL(1), I recommend implementing the parse algorithm, which is just having a stack where you push non-terminals and refer to the table to produce the AST.