Lab for Automated Reasoning and Analysis LARA

Table-Driven Parser for Balanced Parentheses

First Grammar

It has three alternatives:

S ::= "" | ( S ) | S S
      1.     2.     3.

Goal is to figure out which alternative to use when – convert | into if-then-else.

Compute:

nullable = { S }
first(S) = { ( }
follow(S) = { ( , ) }

Parse Table:

( )
S 1,2,3

Because we have duplicate entries, we cannot use this to build a parser.

Second Grammar

S ::= "" | F S
F ::= ( S )

Again compute:

nullable = { S }
first(S) = { ( }
follow(S) = { ) }
( )
S 2 1
F 1 {}

Recursive Descent Parser

Constructed mechanically:

def S = {
  if (lexer.token==OpenP) { F; S }
  else if (lexer.token==ClosedP) ()
  else error("Expected '(' or ')'")
}
def F = { 
  if (lexer.token==OpenP) {
    lexer.next
    S
    skip(ClosedP)
  } else error("Expected '('")
}

Simplified:

def S = if (lexer.token==OpenP) { F; S }
def F = { skip(OpenP); S; skip(ClosedP) }

Top-Down Parser Using a Stack

stack push "S"
while (!stack empty) {
  val X = stack pop
  if (X isTerminal) skip(X)
  else {
    if (X=="S") {
      if (lexer.token==OpenP) stack push "S" push "F"
    } else if (X=="F") stack push ClosedP push "S" push OpenP
  }
}
 
cc10/table-driven_parser_for_balanced_parentheses.txt · Last modified: 2010/10/06 22:48 by vkuncak
 
© EPFL 2018 - Legal notice