Parsing Expression Grammarand Packrat Parsing(Survey)
IPLAS Seminar Oct 27, 2009
Kazuhiro Inaba

This Talk is Based on These Resources The Packrat Parsing and PEG Page (by Bryan Ford)

http://pdos.csail.mit.edu/~baford/packrat/(was active till early 2008)

 A. Birman & J. D. Ullman, “Parsing Algorithms withBacktrack”, Information and Control (23), 1973

 B. Ford, “Packrat Parsing: Simple, Powerful, Lazy,Linear Time”, ICFP 2002

 B. Ford, “Parsing Expression Grammars: A

Recognition-Based Syntactic Foundation”, POPL 2004

Outline What is PEG?
 Introduce the core idea of Parsing ExpressionGrammars

 Packrat Parsing Parsing Algorithm for the core PEG
 Packrat Parsing Can Support More…
 Syntactic predicates Full PEG
 This is what is called “PEG” in the literature.

 Theoretical Properties of PEG
 PEG in PracticeWhat is PEG?
 Yet Another Grammar Formalism
 Intended for describing grammars ofprogramming languages (not for NL, norfor program analysis)

 As simple as Context-Free Grammars

 Linear-time parsable
 Can express:

 All deterministic CFLs (LR(k) languages)
 Some non-CFLs

What is PEG? – Comparison to CFG(Predicate-Free) Parsing

Expression Grammar

Context-Free Grammar A ← B C

 A → B CConcatenation A ← B / CConcatenation

 A → B | C

Prioritized ChoiceUnordered ChoiceWhen both B and C
matches, prefer BWhen both B and C
matches, either will doExample(Predicate-Free) Parsing

Expression Grammar

Context-Free Grammar S ← A a b c

 S → A a b c A ← a A / a A → a A | aS fails on “aaabc”.
SAa

S recognizes “aaabc”

SOops!

Aa



a
Aaabc

AAa

Another Example(Predicate-Free) Parsing

Expression Grammar

Context-Free Grammar S ← E ;

 S → E ;

 if(x>0) if(x>0)/ while ( E ) S/ if ( E ) S else S/ if ( E ) S/…
if(x<9)y=1;
else
y=3; unambiguous| while ( E ) S| if ( E ) S else S| if ( E ) S|…

if(x<9)y=1;
else
y=3; ambiguousFormal Definition
 Predicate-FreePEG G is <N, Σ, S, R>

 N : Finite Set of Nonterminal Symbols
 Σ : Finite Set of Terminal Symbols
 S ∈ N : Start Symbol R ∈ N → rhs : Rules, where rhs::= ε| A (∈ N)| a (∈ Σ)| rhs / rhs| rhs rhs
 Note: A←rhs
stands for R(A)=rhs
 Note: Left-recursion is not allowedSemantics
 [[ e ]] :: String → Maybe String

where String=Σ* [[ c ]] = λs → case s of
 c : t → Just t
 _→ Nothing [[ e1 e2 ]] = λs → case Just t→ [[ e2 ]] t Nothing → Nothing [[ e1 / e2 ]] = λs → case Just t→ Just t Nothing → [[ e2 ]] s
 [[ ε ]] = λs → Just s(for c ∈ Σ)[[ e1 ]] sof[[ e1 ]] sof

 [[ A ]] = [[ R(A) ]] (recall: R(A) is the unique rhs of A)

Example (Complete Consumption)
S←aSb/c [[S]] “acb”
 [[aSb]] “acb”
 [[a]] “acb”

 [[S]] “cb”
 [[aSb]] “cb”

 [[a]] “cb”
 [[c]] “cb”

 [[b]] “b”= Just “”= Just “”= Just “cb”
= Just “b”= Nothing= Nothing= Just “b”= Just “”Example (Failure, Partial Consumption)
S←aSb/c [[S]] “b”
 [[aSb]] “b”= Nothing [[a]] “b”= Nothing= Nothing [[c]] “b”= Nothing [[S]] “cb”

= Just “b”

 [[aSb]] “cb” = Nothing [[a]] “cb”

= Nothing [[c]] “cb”

= Just “b”

Example (Prioritized Choice)S←AaA←aA/a [[ S ]] “aa” = Nothing Because [[ A ]] “aa” = Just “”, [[ A ]] “aa”

= Just “” [[ a ]] “aa”

= Just “a”= Just “” [[ A ]] “a”
…

not Just “a”

“Recognition-Based”
 In “generative” grammars such as CFG,

each nonterminal defines a language(set of strings) that it generates.

 In “recognition-based” grammars,

each norterminal defines a parser(function from string to something)that it recognizes.

Outline What is PEG?
 Introduce the core idea of Parsing ExpressionGrammars

 Packrat Parsing Parsing Algorithm for the core PEG
 Packrat Parsing Can Support More…
 Syntactic predicates Full PEG
 This is what is called “PEG” in the literature.

 Theoretical Properties of PEG
 PEG in Practice[Semantics]

Parsing Algorithm for PEG
 Theorem: Predicate-Free PEG can beparsed in linear time wrt the length ofthe input string.

 Proof By Memoization( All arguments and outputs of [[e]] :: String -> Maybe String

are the suffixes of the input string )[Semantics]

Parsing Algorithm for PEG
 How to Memoize?
 Tabular Parsing [Birman&Ullman73]
 Prepare a table of size |G|×|input|, andfill it from right to left.

 Packrat Parsing [Ford02]
 Use lazy evaluation.

[Semantics]

Parsing PEG (1: Vanilla Semantics)
S ← aS / a doParse = parseS:: String -> Maybe String

 parseA s =case s of 'a':t -> Just t_-> Nothing parseS s = alt1 `mplus` alt2

wherealt1 = case parseA s of
 Just t -> case parseS t of
Just u-> Just uNothing -> Nothing Nothing-> Nothing alt2 = parseA s[Semantics]

Parsing PEG (2: Valued)
S ← aS / a doParse = parseS :: String -> Maybe (Int, String) parseA s =case s of 'a':t -> Just (1, t)
_-> Nothing parseS s = alt1 `mplus` alt2 where

alt1 = case parseA s of
 Just (n,t)-> case parseS t of
Just (m,u)-> Just (n+m,u)Nothing -> Nothing Nothing-> Nothing alt2 = parseA s

[Semantics]

Parsing PEG (3: Packrat Parsing)S ← aS / a type Result = Maybe (Int, Deriv)

 data Deriv= D Result Result

 doParse :: String -> Deriv

 doParse s = d whered= D resultS resultA resultS = parseS d
 resultA = case s of ‘a’:t -> Just (1,next)
_ -> Nothing next= doParse (tail s) …

[Semantics]

Parsing PEG (3: Packrat Parsing, cnt’d)
S ← aS / a type Result = Maybe (Int, Deriv)
 data Deriv = D Result Result
 parseS :: Deriv -> Result
 parseS (D rS0 rA0) = alt1 `mplus` alt2 where

alt1 = case rA0 of
 Just (n, D rS1 rA1) -> case rS1 ofalt1 = case parseA s of

 Just (m, d) -> Just (n+m, d)  Nothing -> NothingJust (m,u)-> Just (n+m,u) Nothing -> Nothing Nothing -> NothingJust (n,t)-> case parseS t ofalt2 = rA0



Nothing -> Nothingalt2 = parseA s

[Semantics]

Packrat Parsing Can Do More
 Without sacrificing linear parsing-time,

more operators can be added. Especially,“syntactic predicates”:
 [[&e]] = λs → case [[e]] s of
 Just _ Nothing→ Just s→ Nothing [[!e]] = λs → case [[e]] s of
 Just _ Nothing→ Nothing→ Just sFormal Definition of PEG
 PEG
 rhs

G is <N, Σ, S, R∈N→rhs> where::=|||||||||εA (∈ N)a (∈ Σ)rhs / rhs
rhs rhs&rhs!rhsrhs?
(eqv. to X where X←rhs/ε)
rhs*(eqv. to X where X←rhs X/ε)rhs+(eqv. to X where X←rhs X/rhs)

Example: A Non Context-Free Language
 {anbncn |n>0}

is recognized by S ← &X a* Y !a !b !c X ← aXb / ab

 Y ← bYc / bc

Example: C-Style Comment
 C-Style Comment Comment← /* ((! */) Any)* */(for readability, meta-symbols are colored) Though this is a regular language, it cannot bewritten this easy in conventional regex.

Outline What is PEG?
 Introduce the core idea of Parsing ExpressionGrammars

 Packrat Parsing Parsing Algorithm for the core PEG
 Packrat Parsing Can Support More…
 Syntactic predicates Full PEG
 This is what is called “PEG” in the literature.

 Theoretical Properties of PEG
 PEG in PracticeTheoretical Properties of PEG
 Two Topics
 Properties of Languages Defined by PEG
 Relationship between PEG and predicate-free PEG

Language Defined by PEG
 For a parsing expression e [Ford04] F(e) = {w∈Σ* [BU73]| [[e]]w ≠ Nothing }B(e) = {w∈Σ* | [[e]]w = Just “” }

 [Redziejowski08]


R. R. Redziejowski, “Some Aspects of Parsing
Expression Grammar”, Fundamenta
Informaticae(85), 2008
 Investigation on concatenation [[e1 e2]] of two PEGsS(e) = {w∈Σ* | ∃u. [[e]]wu = Just u } L(e) = {w∈Σ* | ∀u. [[e]]wu = Just u }Properties of F(e) = {w∈Σ*| [[e]]w ≠ Nothing} F(e) is context-sensitive Contains all deterministic CFL
 Trivially Closed under Boolean Operations
 F(e1) ∩ F(e2) = F( (&e1)e2 ) F(e1) ∪ F(e2) = F( e1 / e2 )
 ~F(e)= F( !e ) Undecidable Problems
 “F(e) = Φ”?

is undecidable
 Proof is similar to that of intersection emptinessof context-free languages
 “F(e) = Σ*”? is undecidable
 “F(e1)=F(e2)”? is undecidable

Properties of B(e) = {w∈Σ*| [[e]]w = Just “”} B(e) is context-sensitive Contains all deterministic CFL
 For predicate-free e1, e2
B(e1)∩B(e2) = B(e3) for some predicate-free e3

 For predicate-free & well-formed e1,e2 where
well-formed means that [[e]] s is either Just”” or NothingB(e1)∪B(e2) = B(e3) for some pf&wf e3
 ~B(e1) = B(e3) for some predicate-free e3 Emptiness, Universality, and Equivalence isundecidable

Properties of B(e) = {w∈Σ*| [[e]]w = Just “”} Forms AFDL, i.e.,markedUnion(L1, L2) = aL1 ∪ bL2
 markedRep(L1) = (aL1)*
 marked inverse GSM (inverse image of a stringtransducer with explicit endmarker) [Chandler69] AFDL is closed under many otheroperations, such as left-/right- quotients,
intersection with regular sets, …


W. J. Chandler, “Abstract Famlies of DeterministicLanguages”, STOC 1969

Predicate Elimination
 Theorem: G=<N,Σ,S,R> be a PEG such thatF(S) does not contain ε. Then there is anequivalent predicate-free PEG.

 Proof (Key Ideas): [[ &e ]] = [[ !!e ]] [[ !e C ]] = [[ (e Z / ε) C ]] for ε-free C where Z = (σ1/…/σn)Z / ε,{σ1, …,σn}=Σ

Predicate Elimination
 Theorem: PEG is strictly more powerful thanpredicate-free PEG

 Proof:

We can show, for predicate-free e, ∀w.( [[e]] “” = Just “”⇔[[e]] w = Just w )by induction on |w| and on the length of derivation

Thus we have“”∈F(S)⇔ F(S)=Σ*but this is not the case for general PEG (e.g., S←!a)Outline What is PEG?
 Introduce the core idea of Parsing ExpressionGrammars

 Packrat Parsing Parsing Algorithm for the core PEG
 Packrat Parsing Can Support More…
 Syntactic predicates Full PEG
 This is what is called “PEG” in the literature.

 Theoretical Properties of PEG
 PEG in PracticePEG in Practice Two Topics When is PEG useful?
 Implementations

When is PEG useful?
 When you want to unify lexer and parser

For packrat parsers, it is easy.
 For LL(1) or LALR(1) parsers, it is not.
list<list<string>>
Error in C++98, because >> is RSHIFT, not two
closing angle brackets
 Ok in Java5 and C++1x, but with strange grammar(* nested (* comment *) *)s = “embedded code #{1+2+3} in string”

Implementations

Performance (Rats!)
 R. Grimm, “Better Extensibility through ModularSyntax”, PLDI 2006
Parser Generator for PEG, used, e.g., for Fortress

Experiments
on Java1.4grammar,with sourcesof size
0.7 ～ 70KB

PEG in Fortress Compiler Syntactic Predicates are widely used(though I’m not sure whether it is essential, due tomy lack of knowledge on Fortress…)/* The operator "|->" should not be in the left-hand sides of map
expressions and map/array comprehensions.
*/

String mapstoOp =!("|->" w Expr (w mapsto / wr bar / w closecurly / w comma)) "|->" ;/* The operator "<-" should not be in the left-hand sides ofgenerator clause lists. */String leftarrowOp = !("<-" w Expr (w leftarrow / w comma)) "<-";

Optimizations in Rats!

Summary Parsing Expression Grammar (PEG) …
 has prioritized choice e1/e2, rather thanunordered choice e1|e2.

 has syntactic predicates &e and !e, which

can be eliminated if we assume ε-freeness.

 might be useful for unified lexer-parser.
 can be parsed in O(n) time, by memoizing.