polimd/Formal Languages and Compilers/lesson_04.md

FLC - lesson 04

Luca Oddone Breveglieri

12 october 2015

Free Grammars pt.I

Grammars

Are meant to overcome the limits of regexp
Are composed by:

• A starting language
• A set of rules which can be applied a finite number of times

A language can be defined by rules that after multiple applications allow to generates all and only the phrases in the language

Context-free grammars

example 1:

Language $$L={uu^R|u\in {a,b}^}={\varepsilon,aa,bb,abba,baab,...,abbbba,...}$$ Grammar rules $\text{frase}\rightarrow \varepsilon$ - The empty string is a valid phrase $\text{frase}\rightarrow a\;\text{frase}\;a$ - A phrase encloses in a, a it's a phrase $\text{frase}\rightarrow b\;\text{frase}\;b$ - A phrase encloses in b, b it's a phrase <!----> Derivation chain $$\text{frase}\Rightarrow a\;\text{frase}\;a$$ Lista, frase are non-terminal symbols

example 2:

The metalanguage of regular expressions

alphabet $\Sigma_{r.e.}={a,b,\cup,,\emptyset,(,)}$ <!----> syntax $1.\;espr \rightarrow\emptyset$ $2.\;espr \rightarrow a$ $3.\;espr \rightarrow b$ $4.\;espr \rightarrow (espr\cup espr)$ $5.\;espr \rightarrow (espr\;espr)$ $6.\;espr \rightarrow (espr)^$ <!---->

Backus Normal Form - BNF

Is defined using four entities

• $V$ non-terminal alphabet
• $\Sigma$ terminal alphabet
• $P$ syntactic rules
• $S\in V$ is a particular non-terminal called axiom

Each rule $P$ is a pair $(X,\alpha)$ of:

• $X\in V$ element of the non-terminal alphabet
• $\alpha\in(V\cup \Sigma)^*$ element of terminal or non-terminal alphabet

Some examples are:

• $X\rightarrow\alpha$
• $X\rightarrow\alpha_1|\alpha_2|...|\alpha_n$
• $X\rightarrow\alpha_1\cup\alpha_2\cup...\cup\alpha_n$

Reduction of the grammars

A grammar is in reduced form or simply reduced if both the following conditions hold:

• Every non-terminal A is reachable from the axiom $S\overset{*}{\Rightarrow}\alpha A\beta$
• Every non-terminal A generates a non-empty set of strings $L_A(G)\neq\emptyset$ There exists an algorithm in two phases:
• The first phase identifies the non-terminal symbols that are undefined
• The second phase identifies those that ar unreachable

Phase 1

• Construct the complement set $DEF$ of the defined non-term symbols. $$DEF = V\setminus UNDEF$$
• Initially $DEF$ is set to contain the non-terminal symbols that are expanded by terminal rules $$DEF:={A|(A\rightarrow u)\in P, \text{with}\;u\in\Sigma^}$$ <!---->
• Then the following transformation is applied repeatedly, until it converges $$DEF:=DEF\cup{B|(B\rightarrow D_1D_2...D_n)\in P}$$ Each symbol $D_i$ is either a terminal or belongs to $DEF$

In every iteration of the first phase, two events are possible:

• New non-terminal symbols are identified and added to the set $DEF$
• the $DEF$ set does not change, which means that convergence has been reached, therefore the algorithm terminates.
  

The non-terminal symbols that belong to the $UNDEF$ set can be eliminated along with the rules where they appear.

Phase 2

The identification of the non-terminal symbols that are reachable starting from the axiom $S$ can be reduced to the problem of the existence of a path in the graph associated with the following binary relation produce

$A\overset{produce}{\rightarrow}B \;\;\text{if and only if} \;\;A\rightarrow\alpha B\beta \;\;\text{with}\;\;A\neq B\;\;\;\alpha,\beta\;\text{are any strings}$

The non-terminal $C$ is reachable from the axiom $S$ if and only if the graph of the binary relation produce contains a path from $S$ to $C$

A third property is often required for a grammar to be in the reduced form:

The grammar G may not have circular derivations, which are inessential and moreover give raise to ambiguity

example

$${S\rightarrow a,\;A\rightarrow b}\;\text{reduced to}\;{S\rightarrow a}$$

Recursive grammars

To generate an infinite language, composed of an infinite number of strings, it is necessary to allow derivations of unbounded length, this is called recursive grammar

$$A\overset{n}{\Rightarrow}xAy\;\;n\ge 1\;\;\text{is recursive}$$

Necessary and sufficient condition for a language $L(G)$ to be infinite:

where $G$ is a grammar in the reduced form and does not have any circular derivations, is that $G$ admits recursive derivations

A grammar does not contain recursion (or is recursion-free) if and only if the graph of the binary relation produce is acyclic