LF (k) grammar

from Wikipedia, the free encyclopedia

This article assumes previous knowledge of theoretical computer science and compiler construction .


An LF (k) grammar is a special context-free grammar that forms the basis of an LF (k) parser . Due to the very close relationship, LF (k) grammars are also referred to as strong LL (k) grammars .

The designation LF (k) grammar means that each derivation step is uniquely determined by k symbols of the input ( lookahead ). The question of which non-terminal symbol is to be expanded next with which rule can thus be answered unambiguously with the aid of the next k symbols of the input.

In general, the larger k is chosen, the more powerful the language class becomes, whereby the expressiveness of context-free grammars is never reached. There are thus context-free grammars that are not LF (k) grammars for any k .

Formal definition of LF (k) grammar

A context-free grammar is an LF (k) grammar if and only if for all left derivatives of the form

with and applies .

The following applies to the function used in the definition to determine the first sets:

application

The formal definition of an LF (k) grammar can only be checked with great effort in terms of practical application. Therefore, the test for LF (k) property is carried out using a modified approach.

A reduced context-free grammar is exactly then LF (k) grammar if for all non-terminal symbols and for all productions and with the following applies: .


Explanation: As a result of a word derivation, the start symbol of the context-free grammar was expanded (possibly in several steps). Suppose the next step is to replace the non-terminal symbol A. There are two different rules and available for this. If the intersection specified in the law is empty, then the rule selection can be made clearly.

For this purpose the function is required which calculates the set of all symbols following A.

The test for LL (1) property uses the same approach. A generalization to any k is not possible. This difference separates both grammar forms from one another.

example

The grammar should be examined for its LF (k) property. In other words: For which k is G an LF (k) grammar?

and the amount of productions is

First, the first or follow sets of the non-terminal symbols are determined.

This is followed by a comparison of the quantities as defined above for all productions with the same left-hand rule pages. In this example, the rules are compared with and with .

In the case of the non-terminal symbol S , the sets and are already disjoint. Further considerations for larger k can be omitted.

Only for are the sets to be compared disjoint and thus the deterministic rule selection guaranteed. The example grammar G is therefore an LF (3) grammar.

literature