Aaron Enberg - B.S. Computer Science

CSc 135

PL Assignment 4

Recursive Descent Recognizer

Grammar for Arithmetic Expression
EXP ::= EXP + TERM | EXP - TERM | TERM
TERM ::= TERM * FACTOR | TERM / FACTOR | FACTOR
FACTOR ::= ( EXP ) | DIGIT
DIGIT ::= 0 | 1 | 2 | 3

Enter a valid arithmetic expression with combinations of:
- integers '0', '1', '2', '3',
- arithmetic operators '+', '-', '*', '/',
- parentheses to surround valid expressions '(', ')'
Terminate the input stream with a dollar sign '$'.
Click 'Recognize' to parse the input expression and check if it is accepted by the grammar above.

Example of a valid set:
3-2/(1+3)$
Example of an invalid set:
1+/2$

Report

For implementing the recognizer, I chose to use JavaScript since I've had prior experience in web programming with it. It was a good choice in my opinion because it is a scripting language which does not require a compiler. It is also a human-friendly language (for most simple tasks) so the actual code is similar in readability to pseudocode. One resource that I used as a reference for completing this task was Crafting Interpreter's guide to parsing expressions which touches on a lot more than just coding the parser.

PL Assignment 3

Prolog Exam Problem Contribution

FACTS
drives(bob, camry).
drives(pam, prius).
drives(jim, tacoma).
license(pam, ok).
license(bob, ok).
license(jim, suspended).
license(larry, revoked).
insurance(bob).
insurance(jim).
insurance(pam).

RULES
legalDriver(X):- drives(X, _), license(X, ok), insurance(X).

illegalDriver(X):- drives(X, _), license(X, suspended);
           drives(X, _), \+ insurance(X).

nonDriver(X):- license(X, revoked); \+ drives(X, _).

GOALS
Who is a legal driver and drives a prius?
?-legalDriver(X), drives(X, prius).

Who is a nonDriver?
?-nonDriver(X).

QUERY RUNS


DEDUCTION TREE

PL Assignment 1

(a) Syntax

- A set of rules that defines the combination of symbols that are considered to be a correctly structured document or fragment in a language (Wikipedia).
- The aspects of a programming language that can be modeled by a context-free grammer (Linz).

(b) Semantics

- The rules of a programming language that determine how the meaning of a particualar construct is interpreted (Linz).

(c) Lexical Scanning

- The process of converting a sequence of characters into a sequence of tokens, or strings with certain semantic meaning (Wikipedia).

(d) Parsing and Parser

- Parsing, or syntax analysis, is a way of describing the structure of a sentence through its grammatical derivation (Linz).
- A recursiveDescentRecognizer is a software component that takes input data, usually text, and builds a hierarchical data structure, giving a structural representation of the input and also checking for correct syntax in the process (Wikipedia).