MT1-15-16-ex.4

Group 4. General (4 pts)
Comment the following sentences, indicating if they are true or false, and justifying your answers (if helpful
include illustrative examples to help on justifying your answers):
4.a) [2pts] “The existence of left recursivity in CFG’s make impossible the implementation of them.”.
4.b) [2pts] “The only way to satisfy the precedence of operators in arithmetic and/or logic expressions is to
ensure that the concrete syntax tree respect those precedencies”.


a. Verdadeira

A grammar is LL if and only if for any production A -> a|b, the following two conditions apply.
FIRST(a) and FIRST(b) are disjoint. This implies that they cannot both derive EMPTY
If b can derive EMPTY, then a cannot derive any string that begins with FOLLOW(A), that is FIRST(a) 
and FOLLOW(A) must be disjoint.

An LL(k) grammar is one that allows the construction of a deterministic, descent parser with only k 
symbols of lookahead. The problem with left recursion is that it makes it impossible to determine 
which rule to apply until the complete input string is examined, which makes the required k potentially infinite.
Using your example, choose a k, and give the parser an input sequence of length n >= k:

aaaaaaa...
A parser cannot decide if it should apply S->SA or S->empty by looking at the k symbols ahead because 
the decision would depend on how many times S->SA has been chosen before, and that is information the 
parser does not have.
The parser would have to choose S->SA exactly n times and S->empty once, and it's impossible to decide 
which is right by looking at the first k symbols in the input stream.
To know, a parser would have to both examine the complete input sequence, and keep count of how many 
times S->SA has been chosen, but such a parser would fall outside of the definition of LL(k).
Note that unlimited lookahead is not a solution because a parser runs on limited resources, so there 
will always be a finite input sequence of a length large enough to make the parser crash before producing any output.


b. Falsa

To write a grammar whose parse trees express precedence correctly, use a different nonterminal for each 
precedence level. Start by writing a rule for the operator(s) with the lowest precedence ("-" in our case), 
then write a rule for the operator(s) with the next lowest precedence, etc:

exp    --> exp MINUS exp | term
term   --> term DIVIDE term | factor
factor --> INTLITERAL | LPAREN exp RPAREN
Now let's try using these new rules to build parse trees for 1 - 4 / 2. First, a parse tree that correctly
reflects that fact that division has higher precedence than subtraction:
                        exp
                        /|\
                       / | \
                      /  |  \
                   exp   -   exp
                    |         |
                   term      term
                    |         /|\
                    |        / | \
                  factor term  /  term
                    |     |        |
                    1   factor   factor
                          |        |
                          4        2
Now we'll try to construct a parse tree that shows the wrong precedence:
                                  exp
                                   |
                                  term
	                          /|\
                                 / | \
                                /  |  \
                            term   /   term
                              |         |
                       here we          |
                   want "-" but we    factor
                  cannot derive it      |
                   without parens       2


Diz que basicamente se tiveres uma arvore que respeita a precedência dos operadores então a gramatica 
respeita, mas tens aí um exemplo de uma gramatica que tem uma arvore que respeita e outra que não,
logo não é verdade.