11. Consider the following grammar [15pts] 1. prog → A 2. prog expr ';' 3. expr → ID expr '-' expr expr '/ expr expr '?' expr ':' expr 4. expr 5. expr 6. expr 7. expr → '(' expr ')' *The start symbol is prog; ID and the quoted characters are the terminals. a. Modify the grammar to be LL(1) (unambiguous) b. Show the FIRST and FOLLOW sets

11. Consider the following grammar [15pts] 1. prog → A 2. prog expr ';' 3. expr → ID expr '-' expr expr '/ expr expr '?' expr ':' expr 4. expr 5. expr 6. expr 7. expr → '(' expr ')' *The start symbol is prog; ID and the quoted characters are the terminals. a. Modify the grammar to be LL(1) (unambiguous) b. Show the FIRST and FOLLOW sets

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

1. (a) Write the prefix form for the expression a *- ( b + c ) (b) Write an SDD for the following grammar, which converts infix expressions to prefix expressions. E -> E + T | T T -> T * F | F F -> id | (E) 2. Write the quadruples, triples, and indirect triples for the following expression - (a+b)*(c+d) - (a+b+c)
A) Write a BNF grammar for the language consisting of strings built only of the letters a and b. The strings may have any number of these letters, but the letter combinations bb must be in each string somewhere, and each string must start with a aa. For example, the strings aaabbabbba, aaaababba, and aababbabb are in the language, while a, bba, ababb, aabaa, and bbaa are not. B) Draw the parse tree for string aabbaaba according to the previous grammar: C) Describe, in complete English sentences and “layman’s terms,” the language defined by the following grammar in BNF (start symbol is <S>):<S> ::= <A>a | <B>b<C> ::= c<A> ::= a<A>a | <C><B> ::= b<B>b | <C>
8. L= {w|w e (0,1)* and |w| = 2} 9. L= {w|w € (0,1)* and |w|2 2} 10. L= {w|w e (0,1)* and |w|1}
Problem 1: Write a regular expression that recognizes the following language over the alphabet {a,b}: Any string containing the letters a and b, where the number of letters is not a multiple of three. (Note that 0 is a multiple of three.) Your regular expression should contain only a and b, and the metacharacters (, ), *, +, ? and |. Problem 2: Write a context free grammar that recognizes language from Problem 1. Your start symbol should be named S.
Chomsky Normal Form: Most useful grammars can be translated into a nor-mal form making answers to questions about the language more transparent.
14. Write a BNF grammar that describes an arbitrarily long string of the characters a, b, and c. The string can contain any number of occurrences of these three letters (including none) in any order. The strings "empty", a, accaa, abcabccba, and bbbbb are all valid members of this language.
Consider the following grammar: S➞ ACB/CbB/BaA➞ da/BCB➞ g/∈C➞ h/∈ What is the follow of B?
Please help with this modification:2. Use the logic in that program to design your own Recursive Descent parser in C for the following grammar:S →aABA →Abc | bB →d3. Make sure that you choose at least two strings that pass the grammar and one string that does not pass the grammar just like I did in the model program4. Submit both the code and a screen shot of your results for the choice of strings that you provided. Below is the C code that can be used to implement a Recursive Descent parser for the above grammar/* Recursive Descent Parser for the Expression Grammar:S → (L) |aL' →,SL'|εL → SL'Valid inputs: (a,(a,a)) and (a,((a,a),(a,a)))Invalid inputs:(aa,a)*/#include <stdio.h>#include <string.h>int S(), Ldash(), L();char *ip;char string[50];int main() {printf("Enter the string\n");scanf("%s", string);ip = string;printf("\n\nInput\t\tAction\n ------------------------------\n");if…
arrow_forward Step 1 Context Free Grammar: A formal language that is used to generate all possible strings in a given formal language is called context free grammar. It can be defined as: G=(V, T, P, S) Where G specifies the grammar V specifies the finite set of non-terminal symbols. T specifies the finite set of terminal symbols. P specifies the set of production rules. S specifies the start symbol. The start symbol S is used to derive a string in a context free grammar. It is derived by repeatedly replacing a non-terminal symbol by the right-hand-side production until all the non-terminal symbols have been replaced by the terminal symbols. arrow_forward Step 2 G is a context-free grammar for a language L, and L contains only strings of length 2 or greater. We have to prove that there is a context-free grammar Gd which generates L such that every rule in Gd has the form A -> x1x2, where A is a terminal and each xi is a terminal or a non-terminal. Let the alphabet of…
Q1: Explain the concepts of ambiguity of a grammar. Take an example of your choice and show that the grammar is ambiguous. Draw the parse tree as needed. Q2: Select three flow control statements from C-programming, or from any other programming of your choice, and explain how the relevant grammars are written.
Write a GO grammar expression where: 1. An expression is either an id (you may assume this token has been defined) or a combination of subexpressions using the **, ^ and $ operators 2. ** is a binary infix operator, while ^ is a unary operator that appears before an expression and $ is an operator that appears after an expression 3. ^ has precedence over **, which has precedence over $ 4. ** has right-associativity
Q1. Design Context free grammars for the following: 1. {w € {0, 1}*| w contains at least three 1s } 2. { w € {0, 1}* | w =w* and |w| is even } Where R indicates reverse. 3. { w e {0, 1}*| the length of w is odd and the middle symbol is 0 } 4. { a'b'c* | i, j, k 20, and i = j or i > k} 5. { a'bic* |i, j, k20 and i +j=k } 6. The language A of strings of properly balanced left and right brackets: every left bracket can be paired with a unique subsequent right bracket, and every right bracket can be paired with a unique preceding left bracket. Moreover, the string between any such pair has the same property. For example, [] [[ D]E A. 7. { a"b" | n21} 8. L= {w|w E (0,1)* and |w| = 2} 9. L= {w|w E (0,1)* and |w|2 2} 10. L= {w|w E (0,1)* and |w| 1} 17.{ a"bm*c" | n,m 21}