O'Reilly logo

Formal Languages and Automata Theory by K.V.N. Sunitha

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required