Question: Given the following grammar,
<program> ::= <stmt_list>
<stmt_list> ::= <stmt> | <stmt> <stmt_list>
<stmt> ::= <declaration_stmt> | <assign_stmt>
<declaration_stmt> ::= var <ident_list> ;
<ident_list> ::= <var_id> | <var_id> , <ident_list>
<var_id> ::= a | b | c | d | e
<assign_stmt> ::= <var_id> = <expression> ;
<expression> ::= <expression> + <expression>
| <constant> | <var_id>
<constant> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
a) Drive the string "var a, b, c; a = a + b + 5;",
using the rightmost derivation to show that it is in the language.
b) Show its parse tree.
c) Is the grammar ambiguous or not?
Answer:
a) The leftmost derivation:
<program> ⇒ <stmt_list>
⇒ <stmt> <stmt_list>;
⇒ <stmt> <stmt>;
⇒ <stmt> <assign_stmt>;
⇒ <stmt> <var_id> = <expression> ;
⇒ <stmt> <var_id> = <expression> + <expression>> ;
⇒ <stmt> <var_id> = <expression> + <constant> ;
⇒ <stmt> <var_id> = <expression> + 5 ;
⇒ <stmt> <var_id> = <expression> + <expression> + 5 ;
⇒ <stmt> <var_id> = <expression> + <var_id> + 5 ;
⇒ <stmt> <var_id> = <expression> + b + 5 ;
⇒ <stmt> <var_id> = <var_id> + b + 5 ;
⇒ <stmt> <var_id> = a + b + 5 ;
⇒ <stmt> a = a + b + 5 ;
⇒ <declaration_stmt> a = a + b + 5 ;
⇒ var <ident_list> ; a = a + b + 5 ;
⇒ var <var_id> , <ident_list> ; a = a + b + 5 ;
⇒ var <var_id> , <var_id> , <ident_list> ; a = a + b + 5 ;
⇒ var <var_id> , <var_id> , <var_id ; a = a + b + 5 ;
⇒ var <var_id> , <var_id> , c ; a = a + b + 5 ;
⇒ var <var_id> , b , c ; a = a + b + 5 ;
⇒ var a , b , c ; a = a + b + 5 ; ✓
23 sentential forms.
b) The parse tree
c) It is ambiguous,
becuase <expression> ::= <expression> + <expression> rule can be expanded from
the left <expression> or the right one leading to two different parse trees.
Question: Write a lex file to generate a scanner that will print EU_DATE or USA_DATE, if the input is a string representing a date in European or United States format, respectively. For other strings, it will display NOT_A_DATE.
You may assume the year value is grater than 1000, less than 10000.
Examples of USA date format: 2/19/2019, 10/29/1923, 04/20/1920, 1.2.2025.
Examples of EU date format: 19.2.2019, 29.10.1923, 20.04.2019, 2/1/2025.
Answer:
%option main
day 0?[1-9]|[12][0-9]|3[0-1]
month 0?[1-9]|1[0-2]
year [1-9][0-9][0-9][0-9]
%%
{month}\/{day}\/{year} printf("USA_DATE");
{day}\.{month}\/{year} printf("EU_DATE");
.* printf("NOT_A_DATE");