Answer to Question #186881 in C for Tom Boyle

Question

These are the theory questions about Compilers:

1. What is LL1 parsing? Define the meaning of each character of LL1.

2. Which part of a compiler needs to be modified if the precedence of operations changes?

3. Regular languages are closed under regular operations. What does this mean?

4. What is Subset Construction?

5. What is left factoring and why is it applied on Context-Free Grammars?

Answer 1

1)

To construct the Parsing table, we have two functions: 

1: <strong style="margin: 0px; padding: 0px; border: 0px; vertical-align: baseline;">First()</strong>: If there is a variable, and from that variable if we try to drive all the strings then the beginning Terminal Symbol is called the first. 

2: <strong style="margin: 0px; padding: 0px; border: 0px; vertical-align: baseline;">Follow()</strong>: What is the Terminal Symbol which follow a variable in the process of derivation. 

Now, after computing the First and Follow set for each Non-Terminal symbol we have to construct the Parsing table. In the table Rows will contain the Non-Terminals and the column will contain the Terminal Symbols. 

All the Null Productions of the Grammars will go under the Follow elements and the remaining productions will lie under the elements of First set. 

Now, let’s understand with an example. 

Consider the Grammar: 

 

E --> TE'
E' --> +TE' | e                 
T --> FT'
T' --> *FT' | e
F --> id | (E)

**e denotes epsilon

2)

Preprocessor

3)

• Theorem 1.25: The class of Regular Languages is closed under the union operation
  
• Theorem 1.25 (restated): If A and B are regular languages, then so is A ∪ B
  
• Since A and B are regular, there are machines M_A and M_B that recognize them.
  
• Proof Idea:
• Use FSMs M_A and M_B to create FSM M₃
• M₃ recognizes the union of A and B
• M₃ accepts a string if either M_A or M_B does.
• M₃ simulates running both machines simultaneously.
• Intuition: keep one finger in each machine during execution

• Example 1: Regular languages A = {0}* and B = {1}*, Σ = {0,1}
• What machine recognizes A?
• What machine recognizes B?

• Draw FSM M₃ that recognizes A ∪ B
• Define Q₃, new states that represent cross products of states
• Define Σ, q₀, F
• Define Delta: Domain, codomain, and operations

• Example 2: Regular languages C = 0w and D = w0 where w is a non empty string from Σ
• What machine recognizes C?
• What machine recognizes D?
  
• Draw FSM M₃ that recognizes C ∪ D

4)

1. The Subset Construction Formal Definition of Nondeterministic Finite Automata A nondeterministic finite automaton (NFA) is a five-tuple N = (Q, 1:, d, S, F),

where everything is the same as in a deterministic automaton, except for the following two differences. • S is a set of states, that is, S ~ Q, instead of a single state. The elements of S are called start states. • d is a function d : Q x 1: -+ 2Q , where 2Q denotes the power set of Q or the set of all subsets of Q: 2Q ~f {A I A !; Q}. Intuitively, d(p, a) gives the set of all states that N is allowed to move to from p in one step under input symbol a. We often write a p--+ q D. C. Kozen, Automata and Computability © Springer Science+Business Media, Inc. 1997 The Subset Construction 33 if q E ~(p,a). The set ~(p,a) can be the empty set 0. The function ~ is called the transition function. Now we define acceptance for NFAs. The function ~ extends in a natural way by induction to a function & : 2Q x E* -+ 2Q according to the rules ~ def ~(A,€) = A, ~ def U ~(A,xa) = ~(q,a). (6.1) (6.2) Intuitively, for A ~ Q and x E E*, &(A, x) is the set of all states reachable under input string x from some state in A. Note that ~ takes a single state as its first argument and a single symbol as its second argument, whereas & takes a set of states as its first argument and a string of symbols as its second argument. Equation (6.1) says that the set of all states reachable from a state in A under the null input is just A. In (6.2), the notation on the right-hand side means the union of all the sets ~(q,a) for q E &(A,x); in other words, r E &(A,xa) if there exists q E &(A,x) such that r E ~(q,a). x a p -----------------+ q _ r Thus q E &(A,x) if N can move from some state pEA to state q under input x. This is the nondeterministic analog of the construction of (; for deterministic automata we have already seen. Note that for a E E, &(A,a) = U ~(p,a) PEa(A,<) = U ~(p,a). pEA The automaton N is said to accept x E E* if &(8,x)nF:;60. In other words, N accepts x if there exists an accept state q (i.e., q E F) such that q is reachable from a start state under input string x (i.e., q E &(8, x)). We define L(N) to be the set of all strings accepted by N: L(N) = {x E E* I N accepts x}. 

5)

s = a | b
b = c d
c = (e | f) g
e = a | h

So we have two basic variations, the terminal a optionally followed by g then d, or else one of h or f always followed by g then d.

So we have

s =  b' | c'
b' = a | a g d
c' = (h | f) g d

or, pulling the common g d sequence into its own production

s =  b' | c'
b' = a | a e'
c' = (h | f) e'
e' = g d

We can then pull a up as a common starting symbol in b' by introducing an E (empty) option:

s =  b'' | c'
b'' = a (e' | E)
c' = (h | f) e'
e' = g d

The grammar is now unambiguous.