<assign> à<id> = <expr>
<id> àA | B | C
<expr> à<expr> + <expr>
| <expr> * <expr>
| ( <expr> )
| <id>
<S> à[ <B>, <S> ] | <B>
<B> à<C> | ( <B> )
<C> à a | b | c
Which of the following are valid sentences in this language? Give parse trees if possible.
a) (((b) ))
b) [ a, (b) ]
c) [ [c,c], [b,b] ]
a = 2b + 1;
b = a – 3 {b < 0}
Answer to the first question is provided below. Please ask other questions in a separate post.
Binary search algorithm:
# Iterative Binary Search
def binarySearch(arr, l, r, x):
while l <= r:
mid = int(l + (r - l)/2)
print(ord(arr[mid]),ord(x) )
if arr[mid] == x:
return mid
elif arr[mid] > x:
l = mid + 1
else:
r = mid - 1
return -1
arr = [ 'A', 'C', 'K', 'L', 'M' ]
x = 'K'
result = binarySearch(arr, 0, len(arr)-1, x)
if result != -1:
print("Element is present at index ",result)
else:
print("Element is not present in array")
# Recursive binary search.
def binarySearch (arr, l, r, x):
if r >= l:
mid = int(l + (r - l)/2)
if arr[mid] == x:
return mid
elif arr[mid] > x:
return binarySearch(arr, l, mid-1, x)
else:
return binarySearch(arr, mid+1, r, x)
else:
return -1
# Test array
arr = [ 'A', 'C', 'K', 'L', 'M' ]
x = 'K'
# Function call
result = binarySearch(arr, 0, len(arr)-1, x)
if result != -1:
print("Element is present at index ",result)
else:
print("Element is not present in array")
OUTPUT:
In the recursive search algorithm, the number of comparisons is one while in the iterative algorithm of binary search, the number of comparisons is 3. Thus, the recursive is faster than iterative one in worst cases. But in bast cases, like if the element is present at the first index then the iterative algorithm will be faster.
(20 pts) To understand the value of recursion in a programming language: implement the binary search...
2. Consider the following grammar: <assign> à <id> = <expr> <id> à A | B | C <expr> à <id> + <expr> | <id> * <expr> | ( <expr> ) | <id> Show a parse tree and leftmost derivation for the following statements: (a) A = ( A + B ) * C (b) A = A * ( B + C ) 3. [10 Points] Show that the following grammar is...
(8) (3 marks) Write BNF grammar rules for a language that is comprised only of sentences described as follows: symbol, fol symbols orjust onéx symbol, A sequence of one or more occurrences of an a lowed by either zero or morez followed by a sequence of one or more b symbols. (9) (1 mark) The following fragment of grammar describes the syntax of the exponentiation operator. What is the associativity ot the operator as detined here? factor | expr factor...
1. (p. 2-3.) Which of the following is NOT a reason for studying concepts of programming languages according to Sebesta? a. Increased capacity to express ideas. b. Improved background for choosing appropriate languages. c. Increased ability to design new languages. d. Increased ability to learn new languages. 2. (p. 5-6.) What programming language has dominated scientific computing over the past 50 years? a. FORTRAN b. ALGOL c. SNOBOL d. PL/I 3. (p. 6.) What programming language has dominated artificial intelligence...
I need help with the following problems, any help you can provide is deeply appreciated! CSC 404 Exam 1 Question I continued - 9. The syntax rules for most languages ignore spaces. An exception is which tises indents and therefore spaces to form the indents) to group statements (a) FORTRAN (6) Pascal (e) Python (d) Lip (e) C++ 10. Identifiers, constants and operators are typical examples of (a) tokens. (b) leafons. (c) signifiers. (d) lexicons. (e) parsicles. 0) non-terminals. 11....