1

LL(1) Parser Generator

 1 year ago
source link: https://www.cs.princeton.edu/courses/archive/spring20/cos320/LL1/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

LL(1) Parser Generator

LL(1) Parser Visualization

Write your own context-free grammar and see an LL(1) parser in action!

Written by Zak Kincaid and Shaowei Zhu based on http://jsmachines.sourceforge.net/machines/ll1.html

1. Write your LL(1) grammar (empty string '' represents ε):

Valid LL(1) Grammars

For any production S -> A | B, it must be the case that:

  • For no terminal t could A and B derive strings beginning with t
  • At most one of A and B can derive the empty string
  • if B can derive the empty string, then A does not derive any string beginning with a terminal in Follow(A)

Formatting Instructions

  • The non-terminal on the left-hand-side of the first rule is the start non-terminal
  • Write each production rule in a separate line (see example to the left)
  • Separate each token using whitespace
  • $ is reserved as the end-of-input symbol, and S is reserved as an artificial start symbol. The grammar is automatically augmented with the rule S ::= start $

Debugging

  • More information about the parser construction is printed on the console
  • The source code follows the pseudocode in lecture. In particular, see computeNullable, computeFirst, computeFollow, and computeLL1Tables

Generate tables

2. Nullable/First/Follow Table and Transition Table

NonterminalNullable?FirstFollow
S✖(, id
E✖(, id), $
E'✔+), $
T✖(, id+, ), $
T'✔*+, ), $
F✖(, id+, *, ), $
$+*()id
SS ::= E $S ::= E $
EE ::= T E'E ::= T E'
E'E' ::= εE' ::= + T E'E' ::= ε
TT ::= F T'T ::= F T'
T'T' ::= εT' ::= εT' ::= * F T'T' ::= ε
FF ::= ( E )F ::= id

3. Parsing

Token stream separated by spaces:

Start/Reset Step Forward

Stack
Remaining Input
Rule

Partial Parse Tree


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK