Menu
Is there a good resource online with a collection of grammars for some of the major parsing algorithms (LL(1), LR(1), LR(0), LALR(1))? I've found many individual grammars that fall into these families, but I know of no good resource where someone has written up a large set of example grammars.
Does anyone know of such a resource?
246
LR Parser is one of the bottom up parser which uses parsing table (dynamic programming) to obtain the parse tree form given string using grammar productions. First L of LL is for left to right and second L is for leftmost derivation. L of LR is for left to right and R is for rightmost derivation.
A → a is LALR(1) but not SLR(1). Then, the LALR(1) parsing table can be obtained by merging items with common first components, In this problem, no merging occurs. That is, the final LALR(1) parsing table is the same as the LR(1) one. Thus, the given grammar is LALR(1).
In the name LL(1), the first L stands for scanning the input from left to right, the second L stands for producing a leftmost derivation, and the 1 stands for using one input symbol of lookahead at each step to make parsing action decision.
LR parser is a bottom-up parser for context-free grammar that is very generally used by computer programming language compiler and other associated tools. LR parser reads their input from left to right and produces a right-most derivation.
Examples from wikipedia
grammar
S -> F S -> ( S + F ) F -> a input
( a + a ) parsing steps
S -> "(" S "+" F ")" -> ( "F" + F ) -> ( "a" + F ) -> ( a + "a" ) grammar
(1) E → E * B (2) E → E + B (3) E → B (4) B → 0 (5) B → 1 input
1 + 1 parsing steps
need to build a parser table and traverse through states. grammar
S’ -> S S S -> C C C -> c C | d input
cd parsing steps
large table grammar
A -> C x A | ε B -> x C y | x C C -> x B x | z input
xxzxx parsing steps
traverse large parser table You may also want to have a look at
56
Parsing Techniques - A Practical Guide has several examples (i.e. probably half a dozen or so per type) of almost every type of grammar. You can purchase the 2nd edition book, although the 1st edition is available for free on the author's website in PDF form (near bottom of link).
The author also has some test grammars that he bundles with his code examples from the second edition, which can be found here.
Note: all of these grammars are small (less than a couple dozen rules), because of this obviously being a published book.
27
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
