<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> ::= x | y | z <assign_stmt> ::= <var_id> = <expression> ; <expression> ::= <expression> * <expression> | <constant> | <var_id> <constant> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
drive the string "var x, y; x = 2 * x * y;
",
using the rightmost derivation to show that it is in the language.
Answer:
The rightmost 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> * <expression> * <expression> ; ⇒ <stmt> <var_id> = <expression> * <expression> * <var_id> ; ⇒ <stmt> <var_id> = <expression> * <expression> * y ; ⇒ <stmt> <var_id> = <expression> * <var_id> * y ; ⇒ <stmt> <var_id> = <expression> * x * y ; ⇒ <stmt> <var_id> = <constant> * x * y ; ⇒ <stmt> <var_id> = 2 * x * y ; ⇒ <stmt> x = 2 * x * y ; ⇒ <declaration_stmt> x = 2 * x * y ; ⇒ var <ident_list> ; x = 2 * x * y ; ⇒ var <var_id> , <ident_list> ; x = 2 * x * y ; ⇒ var <var_id> , <var_id> ; x = 2 * x * y ; ⇒ var <var_id> , y ; x = 2 * x * y ; ⇒ var x , y ; x = 2 * x * y ; ✓
<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> ::= x | y | z <assign_stmt> ::= <var_id> = <expression> ; <expression> ::= <expression> / <expression> | <constant> | <var_id> <constant> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
a) Show a parse tree for drive the string "var x, y; x = 2 / x / y; "
b) Show that the grammar is ambiguous.
c) How can the grammar be disambiguated?
Answer:
a)
b) Since the following is a different parse tree for the same string, the grammar is ambiguous.
c) Considering that the / operator is left associative, the following production rule
<expression> ::= <expression> / <expression>should be replaced by the following left recursive rules
<expression> ::= <expression> / <constant> <expression> ::= <expression> / <var_id>
lex
specification 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 greater than 1000.2/19/2019
, 10/29/1923
, 04/20/1920
.19.2.2019
, 29.10.1923
, 20.04.2019
.
Answer:
%option main day 0?[1-9]|[1-2][0-9]|3[0-1] month 0?[1-9]|1[0-2] year [1-9][0-9][0-9][0-9] %% {day}\.{month}\.{year} printf("EU_DATE"); {month}\/{day}\/{year} printf("USA_DATE"); .* printf("NOT_A_DATE");
yacc
specification file with tokens
corresponding to the unique letters in your last name, only.
For example, in my case, the tokens are G, U, V, E, N, I, R.
a) Write the grammar rules in such a way that the grammar will have a shift/reduce conflict if your ID is odd, a reduce/reduce conflict if your ID is even.
b) Indicate on what token the conflict will occur.
c) Is your grammar ambiguous? Why?
Answer:
a) Shift/reduce conflict:
%token G U V E N I R %% start: x V | y U N; x: G U; y: G ;
b) The token causing the conflict is U
c) The grammar is unambiguous. The language of the grammar is L={GUV, GUN}. Each of the words in the language has exactly one poarse tree.
start start / \ / | \ x V y U N / \ | G U G
Or,
a) Reduce/reduce conflict:
%token G U V E N I R %% start: x U V | y U N; x: G ; y: G ;
b) The token causing the conflict is U
c) The grammar is unambiguous. The language of the grammar is L={GUV, GUN}. Each of the words in the language has exactly one poarse tree.
start start / | \ / | \ x U V y U N | | G G
<script> a = 3; console.log ("global, a="+a); function foo (arg) { var a = arg * 2; console.log("foo, a="+a+" b="+b); var b= 7; { console.log ("block, a="+a+" b="+b); var b= b*2; console.log ("block, a="+a+" b="+b); let c = b *3; console.log ("block, a="+a+" b="+b+" c="+c); } console.log("foo, a="+a+" b="+b); } // foo() foo(a+2) console.log ("global, a="+a); </script>
Answer:
global, a=3 foo, a=10 b=undefined block, a=10 b=7 block, a=10 b=14 block, a=10 b=14 c=42 foo, a=10 b=14 global, a=3
a) Write a simple Python code segment that finds and displays the index of the first row that has nothing but all zeros, of an n by n 2D integer list named matrix. If the matrix does not have such a row, the program segment should print a message indicating this case (this question is a modified version of the programming exercise 5, at the end of Chapter 8).
What is the output of your code segment for the following cases? :
b) matrix = [[1,2,3,4],[0,3,1,5],[0,0,0,0],[0,0,0,0]]
c) matrix = [[1,2,3,4],[3,0,4,5],[0,0,1,0],[1,0,0,0]]
Answer:
a)
n = len(matrix) for i in range(n): for j in range(n): if matrix[i][j] !=0: break else: print("The index of the first all-zero row is", i) break else: print("No all-zero row")
b)
First all-zero row is 2
c)
No all-zero row
a)def foo (par): par = 7 print("foo: par=",par) act = 5 foo(act) print("after foo: act=", act) |
b)act=5 def foo (par): par = 7 print("foo: par=",par) foo(act + 10) print("after foo: act=", act) |
c)act= [1,2,3] def foo(par): par[0] = 315 print("foo: par=",par) foo(act) print("after foo: act=", act) |
d)act= {"a":1, "b":2, "c":3} def foo(par): par["d"] = 315 print("foo: par=",par) foo(act) print("after foo: act=", act) |
e)act= (1,2,3) def foo(par): par[0] = 315 print("foo: par=",par) foo(act) print("after foo: act=", act) |
f)def foo(*par) : par[1] = 315 print("foo: par=", par) return par res=foo(1,2,3) print("after foo: res=", res) |
Answer:
a)foo: par= 7 after foo: act= 5 |
b)foo: par= 7 after foo: act= 5 |
c)foo: par= [315, 2, 3] after foo: act= [315, 2, 3] |
d)foo: par= {'a': 1, 'b': 2, 'c': 3, 'd': 315} after foo: act= {'a': 1, 'b': 2, 'c': 3, 'd': 315} |
e)TypeError: 'tuple' object does not support item assignment after foo: act= (1, 2, 3) |
f)TypeError: 'tuple' object does not support item assignment NameError: name 'res' is not defined |
1) What is the yield of the following s-expressions, written in Scheme?
(null? (cddr '(a b)))
(list? (cddr '(a b)))
(member 'a '((a b)))
(append '(a b) (cdr '(a b)))
(map (lambda (n m) (+ n (* 2 m))) '(3 5) '(2 4))
2) Define a recursive function in the Scheme language, called counta
,
that takes an atom and a list of atoms and returns the number of occurrences of the atom in the list.
For example, (counta 'x '(a b x c x))
should yield 2
,
since the atom x
occurs twice in the list (a b x c x)
.
Answer:
1) The yields are
#t
#t
#f
(a b b)
(7 13)
2) A possible recursive definition for function counta
:
(define (counta atm lst) (cond ((null? lst) 0) ((eq? atm (car lst)) (+ 1 (counta atm (cdr lst)))) (else (counta atm (cdr lst)))))