CSCI_4350_2_8_2019.md

CSCI_4350_2_8_2019.md

Procedure for Expr'

1. If the current input token is + or -, get the next token and call the Term procedure, then call the Expr' procedure
2. If the current input token is EOF or ), return from the procedure
3. If the current input token is anything else, report an error

Table-driven top-down parser enforces syntex rules using a parse table

LL1 parse table

• The rows of the parse table are introduced by nonterminal symbols
• The columns of the parse table are indexed by the terminal symbols
• The entities in the table contain production #s or an indication that a parse error has occured

	EOF	+	-	*	/	(	)	id	num
Goal						0		0	0
Expr						1		1	1
Expr'	4	2	3				4
Term						5		5	5
Term'	8	8	8	6	7		8
Factor						9		11	10

Parsing Algorithm (for the table method)

1. Push EOF
2. Loop where the stack is popped to get the current symbol
   1. If the symbol is a terminal, try to match with current input; EOF match -> end of parse
   2. If the symbol is a non-terminal look up entry
      1. If parse table entry indicates error generate a parse error
      2. Otherwise push symbols on RHS of the indicated production on stack in reverse order

	EOF	+	-	*	/	(	)	id	num	Stack
Goal						0		0	0
Expr						1		1	1
Expr'	4	2	3				4
Term						5		5	5
Term'	8	8	8	6	7		8
Factor						9		11	10