Formal languages

Question 1

PDA

Answer 1

We want to find other representation of a context free language in order to solve the membership problem efficiently.

The problem is that with context free languages if they are complex, the tools become less and less efficient, some languages aren’t even feasible to manipulate.

Pushdown automaton: finite state automaton with stack memory structure:

{Q, Σ, Γ, 𝛿, q₀, Z₀, F}

• Q: finite (non-𝛆) set of states
• Σ: alphabet of input symbols
• Γ: alphabet of stack symbols (the two alphabet could be overlapped, fully, partially or none at all)
• 𝛿: transition function
  
  • different domain compared to the NFA definition
  • 𝛿: Q x (Σ ∪ {𝛆}) x Γ → 𝒫({(p, 𝛾) | p ∈ Q; 𝛾 ∈ Γ^*})
    
    • p is the new state
    • 𝛾: 0 or more symbols are pushed to the stack
• q₀: start state (q₀ ∈ Q)
• Z₀: start stack symbol (Z₀ ∈ Γ)
• F: set of final states (F ⊆ Q)

A language is accepted by a final state by the PDA.

A language is accepted by empty stack.

Question 2

NFA

Question 3

Equations tricks

Answer 3

Question 4

Context-free languages venn diagram

Answer 4

Question 5

LL(1) grammars

Answer 5

A grammar is said to be LL(1) if its predictive parsing table has no multily-defined entries:

• whenever A → 𝛂 | β then
  
  • First(𝛂) ⋂ First(β) = ∅
  • at most one of 𝛂 and β is nullable
  • if 𝛂 is nullable then First(β) ⋂ Follow(A) = ∅

No ambiguos or left-recursive grammar can be LL(1).

LL(1) parser:

• scans the input from left to right (L)
• constructs a leftmost derivation (L)
• uses 1 lookahead input symbols in making parsing decisions.

The class of languages that can be parsed with LL(1) parsers a proper subset off the deterministic CFL’s.

Question 6

SA: left recursive grammars

Answer 6

• a production like A → A 𝛂 is called left-recursive
• a grammar is left recursive if it can generate a derivation A => *A 𝛂
• a left-recursive gramma can cause a top-down parer to go into an infinite loop

Replacing left-recursive productions:

A → A 𝛂 | β ===

• A → β R
• R → 𝛂 R | 𝛆

Question 7

SLR

Answer 7

SLR parsing tables for the same languages are much smaller respect to LR(1) parsing tables (several hundred states) but can contain conflicts.

Question 8

LR

Answer 8

• LR(0) parser
  
  • scans the input from left to right (L)
  • constructs a rightmost derivation in reverse (R)
  • uses 0 lookahead input symbols in making parsing decisions
  • parsable langagues are a subset of deterministc CFL’s
  • • LR(1) parser
  • scans the input from left to right (L)
  • constructs a rightmost derivation in reverse (R)
  • uses 1 lookahead symbols in making parsing decisions
  • parsable languages are exactly the calss of deterministic CFL’s
  • parsing tables can be very large (several thousand states) for grammars generating common programming languages
• A grammar is LR(0) if the table generated by lr0Table(G) doesn’t include conflicts
  
  • non-ambiguos
• A grammar is LR(1) if the table generated by lr1Table(G) doesn’t include conflicts
  
  • LR(1) grammars are non-ambiguos.
    *

Question 9

LALR(1) parsing

Answer 9

• Look-Ahead LR parser is a simplified version of a canonical LR parser, to parse (separate and analyze) a text according to a set of production rules specified by a formal grammar
• LALR(1) parsing tables have the same states of SLR tables and can conveniently express most programming languages

Core:

• two LR(1) items have the same core if they are identical except for the lookahead symbols

Union:

• a set of LALR(1) items is the union of sets of LR(1) items having the same core.

Conflicts:

• merging state with common cores can never produce shift/reduce conflict which was not present n one of the original states.
• merging may produce reduce/reduce conflicts
• class of parsable languages is a proper subset of the deterministic CFL’s

Question 10

Predictive parsing

Answer 10

• backtracking can be avoided if it is possible to detect wich rule among A → 𝛂₁ | 𝛂₂ | … | 𝛂_n has to be applied, by considering the current input symbol.