Only pseudo code 1. Question 1: Consider the following context free grammar S- a
ID: 3715264 • Letter: O
Question
Only pseudo code
1. Question 1: Consider the following context free grammar S- aSjaSbSje. Prove the following by induction: This CFL language accepts all strings so that every prefix has at least as many a than b and does not accept any other string. Remark: In all the following questions 2,3,4,5 every item can be true or false. So you have to answer all items (namely its not one of these multiple choice exams in which exactly one answer is correct). You need to fully explain all your answers. If you say only yes or no you will get few points if you are correct. Even if you answer is wrong, you will get partial credit for the effort.Explanation / Answer
The proof that all prefixes have at least as many a's as b's follows from the given productions. It is clearly true if the length of the string is 1 (it can only be a single a) or 2 (aa or ab). Assume that it is true for all strings of length up to n. Then, using the given productions, we can construct strings of length n+1. and longer, for which the property clearly holds because we have added an a to any previous prefix. Therefore the property holds for all n. S -> a S | S1 S | epsilon S1 -> a S1 S1 b | epsilon It is easy to verify that this generates the same strings as the original grammar, and the parse tree is always unique, because one b is always associated with the most recent a. Note that the answer is not necessarily unique. If the grammar is ambiguous, it means that we get to choose between possible parses, and each choice is in a sense a different language. For example, given the ambiguous grammar for expressions: E -> E + E | E * E | id We say that the unambiguous grammar we want is: E -> E + T | T, T -> T * T | id because it gives us the proper precedence between the two operators. But that choice is in no way mandated by the grammar. We could just as well choose: E -> E * T | T , T -> T + T | id which generates the same strings, but gives the opposite precedence to operators. 2. Consider a simple language with the following non-terminals: stat-seq : a sequence of statements if-stat : if-statement, both branches have a sequence of statements while-stat : a loop construct, whose body has a sequence of statements func-def : a function definition, whose body is a sequence of statements. ret-stat : a return statement any-stat : any of the above, assignment, goto, etc., Most languages have the semantic requirement that a function body have at least one return statement somewhere, possibly nested in a loop or a conditional statement. For the non-terminals above, write the productions that enforce this rule, namely that a function definition contain at least one return statement. You will want to introduce additional non-terminals. Comment: this kind of semantic restriction can be expressed grammatically, but as you will see, it makes the grammar larger and harder to understand, In practice, this kind of restriction is better stated in prose, and such a rule is not enforced by the parser of a compiler, but by a separate semantic check.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.