CODEWITHSUNDEEP
javaparsingabstract-syntax-tree
Wyvern666
Wyvern666

Reputation: 633

About AST construction in LL1 non recursive parser

I have implemented a LL1 parser in a non recursive approach with a explicit stack.

The following algorithm is from the Dragon Book:

set zp to point to the first symbol of w;
set X to the top stack symbol;
while ( X != $ ) { /* stack is not empty */
    if ( X is a ) 
       pop the stack and advance zp;
    else if ( X is a terminal )
       error();
    else if ( M[X, a] is an error entry )
       error();
    else if ( M[X,a] = X -+ Y1Y2 Yk ) {
       output the production X -+ YlY2 - . Yk;
       pop the stack;
       push Yk, Yk-1,. . . , Yl onto the stack, with Yl on top;

    set X to the top stack symbol;
}

The book says:

The parser is controlled by a program that considers X, the symbol on top of the stack, and a, the current input symbol. If X is a nonterminal, the parser chooses an X-production by consulting entry M[X, a] of the parsing table IM. (Additional code could be executed here, for example, code to construct a node in a parse tree.) Otherwise, it checks for a match between the terminal X and current input symbol a.

However i need more info on how to construct the expression tree nodes under this approach. I have a node hierarchy of UnaryOperator, BinaryOperator, etc but dont know where to instanciate it.

Yet i havent found any simple example of this (with for example the arithmetic language).

Upvotes: 2

Views: 717

Answers (1)

LHP
LHP

Reputation: 180

I have been searching a while for the same information - how to create a parse tree with an LL(1) table-driven non-recursive parse - and found very little.

Just now I found these lecture notes https://parasol.tamu.edu/~rwerger/Courses/434/lec7.pdf in which it is proposed that for every terminal or nonterminal, the corresponding parse tree node is also pushed onto the stack. It does seem wasteful somehow, though. Here is the proposed algorithm in pseudocode:

TOS ← 0
Stack[tos++] ← eof
Stack[tos++] ← *root node*
Stack[tos++] ← *Start Symbol*
token ← next_token()
X ← Stack[tos]
repeat
  if X is a terminal or eof then
    if X = token then
      pop X
      token ← next_token()
      *pop and fill in node*
    else error()
  else /* X is a non-terminal */
    if M[X,token] = X → Y1Y2...Yk then
      pop X
      *pop node for X
      build node for each child and
      make it a child of node for X*
      push nk,Yk,nk-1,Yk-1...n1,Y1
    else error()
until X = eof

Upvotes: 3

Related Questions