9
LR(k) and LL(1) Grammars
- The most widely used top-down parsers are constructed with LL(1) grammars. The most powerful bottom-up parsers are constructed with LR(k) grammars. The language defined by LR(k) grammars is DCFL.
In this chapter, we introduce a restricted type of CFG called LR(0) Grammar. We discuss the question what are LL(1), LR(0) and LR(1) grammars. Given a grammar, we discuss how to test whether it is LL(1) or LR(0) or LR(1).
9.1 LL(1) Grammar
A grammar that is suitable for LL(1) parser construction is called LL(1) grammar.
Given a grammar, to check whether it is LL(1) or not, we use two functions called First( ) and Follow( ).
Let us now understand the functions First( ) and Follow( ).
The function First (x) (where x is a ...
Get Formal Languages and Automata Theory now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
