5129COMP Programming Language Theory: Compilers, Interpreters & CFG

This assignment delves into fundamental concepts of programming language theory, focusing on context-free grammars (CFGs), compilers, and interpreters. It includes tasks such as deriving strings from a given CFG, constructing parse trees, removing left recursion from a CFG, and differentiating between compilers and interpreters. The assignment also covers practical aspects like converting infix expressions to postfix notation, identifying runtime semantic checks, understanding Turing completeness, and working with floating-point number recognition using regular expressions and DFAs/NFAs. This solved assignment is available on Desklib, a platform offering a wealth of study resources including past papers and solved problems for students.

Programming Language Theory
Name:
Student ID:

QUESTION 2.
(i) [3 marks]
first string
clause
’(’ literal_list ‘)’
‘(’ literal_list op literal | literal ‘)’
‘(‘ literal ‘)’
‘(‘ posneg [a-z] ‘)’
‘(‘ ‘⌐’ [a-z] ‘)’
‘(‘ ‘⌐’ p‘)’
‘(‘ ‘⌐’ p‘)’
‘(‘ ⌐p‘)’
(⌐p)
Second string
clauses ‘∧’ clause
clause ‘∧’ clause
clause ‘∧’ ‘(’ literal_list ‘)’
clause ‘∧’ ‘(‘ literal ‘)’
clause ‘∧’ ‘(‘ posneg [a-z] ‘)’
clause ‘∧’ ‘(‘ ‘⌐’ [a-z] ‘)’
‘(’ literal_list ‘)’ ‘∧’ ‘(‘ ‘⌐’ [a-z] ‘)’
‘(‘ literal ‘)’ ‘∧’ ‘(‘ ‘⌐’ [a-z] ‘)’
‘(‘ posneg [a-z] ‘)’ ‘∧’ ‘(‘ ‘⌐’ [a-z] ‘)’
‘(‘ ε[a-z] ‘)’ ‘∧’ ‘(‘ ‘⌐’ [a-z] ‘)’
‘(‘ ε[a-z] ‘)’ ‘∧’ ‘(‘ ‘⌐’ [a-z] ‘)’
‘(‘ [a-z] ‘)’ ‘∧’ ‘(‘ ‘⌐’ [a-z] ‘)’
‘(‘ [a-z] ‘)’ ‘∧’ ‘(‘ ‘⌐’ [a-z] ‘)’
‘(‘ c ‘)’ ‘∧’ ‘(‘ ‘⌐’ d‘)’
(c) ∧ (⌐d)

(ii) parse tree for “(a ∨ ⌐d)” derived from the above CFG. [8 marks]
(iii) Rewrite the CFG to an alternative form so that it is not left-recursive.
[8 marks]
When Left-recursion is removed:
clauses → clause R1
R1 → ‘ ’∧ clause R1
| ε
clause → ‘(’ literal_list ‘)’
literal_list → literal R2
R2 → op literal R2
| ε
literal → posneg [a-z]
op → ‘ ’, ‘ ’∨ ∧
posneg → ‘⌐’ | ε
When Simplified:
clauses → clause R1
R1 → ‘ ’∧ clause R1 | ε
clause → ‘(’ literal_list ‘)’
literal_list → literal R2
R2 → op literal R2 | ε
literal → posneg [a-z]
op → ‘ ’, ‘ ’∨ ∧
posneg → ‘⌐’ | ε
clauses
|
clause
|
‘(‘ literal_list ‘)’
|
/ | \
/ | \
literal_list op literal
/ | \
literal | ‘(‘ posneg [a-z] ‘)’
/ | \
‘(‘ posneg [a-z] ‘)’ | \ .
/ | \
‘(‘ ε[a-z] ‘)’ | ‘(‘ ‘⌐’ [a-z] ‘)’
/ | \
‘(‘ a ‘)’ ‘V’ ‘(‘ ‘⌐’ d‘)’

(b) [6 marks]
A compiler is a program that analyze, optimize and translates the source code into
machine code which can easily be executed by that machine. An interpreter is a program
that executes the code, as it gets read.
The outcome of a compiler is an executable that can be executed without the need of the
compiler while an interpreter needs to read the code afresh each time the source code it
executed.
Examples of languages that make use of a compiler include C/C++ and Java while those
that make use of an interpreter include php and python.

QUESTION 3.
(a) Infix expression to postfix form:
(3+4)*(7-9)
[5 marks]
Solution:
Shifting the Operators to the right side, we get:
(34+)(79-)*
since no brackets are needed for expressions in postfix form!
We are left with
34+79-*
(b) [5 marks]
1. Arithmetic errors
2. Array subscript out of bounds error
During compile time, the information about arithmetic errors and array subscript out
of bounds errors is not available. The errors are only made available during runtime
when their usage comes into play. In a well designed program, these types of errors
can be caught as they do raise an exception.
(c) [5 marks]
A programming language is said to be Turing-complete when it is of equivalent
power to any other programming language that is Turing-complete. With that said, a
Turing-complete programming language can be used to develop or implement
anything that another Turing-complete language can. This does not however take
into consideration the difference in source code lines or performance.

(d) [6 marks]
[-1.986 3.0]f
Assumptions made:
All floating point numbers between -1.986 and +3.0 are accepted.
Any other floating point number beyond the range is not accepted.
Alternatively
(-1.986|-0.54|\+180.3|\+2.5678|\+3.0)f
Assumptions made:
Only the specified floating point numbers should be accepted.
Simplified to accept all floats:
^[+-]?([0-9]*[.])?[0-9]+$
(e) [4 marks]
Advantages of DFA in string recognition
i. Constant-space usage.
ii. Trivial linear time.
iii.Reducible to canonical form, hence there exists efficient algorithms to determine
whether a DFA accepts or rejects a given input as expected.
iv.When only a given set of input is required, DFA are more efficient as they will
reject any other form of input.
Disadvantages of DFA.
All recognizable input/automata must be defines. This often limits the capabilities of
recognizing strings in that particular language.
Any problem/string that requires more than a constant space to be solved can not utilize
DFA.
Advantages of NFA
NFA Construction is much easier compared to DFA.
Disadvantages of NFA
May consume more space than DFA which only takes up constant-space.
Mostly imaginary in terms of implementation.

REFERENCES
1. Atasu, K., Hagleitner, C., Polig, R., & Reiss, F. R. (2018). U.S. Patent No. 9,983,876.
Washington, DC: U.S. Patent and Trademark Office.
2. Beyer, D., Gulwani, S., & Schmidt, D. A. (2018). Combining model checking and data-flow
analysis. In Handbook of Model Checking (pp. 493-540). Springer, Cham.