Wingding

a. Recognizing Lexemes

Addition: +
Subtraction: -
Multiplication: *
Division: /
Modulo: %
Less than: <
Greater than: >
Less than Equal To: <=
Greater than Equal To: >=
Equal To: =
Not Equal To: =/=
Not: !
Assignment: <-
Integer Literals: [1-9][0-9]*_(B|S|I|L)
Identifiers: [a-zA-Z_][a-zA-Z_][a-zA-Z_][a-zA-Z_][a-zA-Z_][a-zA-Z_][a-zA-Z_]?[a-zA-Z_]?
loop: O
If: ?
Else: |
And: &
Or: ||
Seperate statements: ;
Begin program: start
End program: stop
Data type declaration: num

b. Production Rules

<program> -> start <stmt_list> stop
<stmt_list> -> <stmt>';'{<stmt>';'}
<stmt> -> <declare> | <if> | <loop> | <assign>
<declare> -> 'num' 'id'
<assign> -> 'id' '<-' <expr>
<if> -> '?' <bool_expr> '{' <stmt_list> '}' ['|' '{' <stmt_list> '}']
<loop> -> 'O' <bool_expr> '{' <stmt_list> '}'

<expr> -> <div> {'^' <div>}
<div> -> <mod> {'/' <mod>}
<mod> -> <mul> {('%' <mul>}
<mul> -> <sub> {'*' <sub>}
<sub> -> <add> {'-' <add>}
<add> -> <fac> {'+' <fac>}
<fac> -> 'id' | 'int_lit' | '(' <expr> ')'

<bool_expr> -> <bequal> {('||'|'&' <bequal>}
<bequal> -> <brel> {('='|'=/=') <brel>}
<brel> -> <bexpr> {('<='|'>='|'<'|'>') <bexpr>}
<bexpr> -> <bdiv> {'^' <bdiv>}
<bdiv> -> <bmod> {'/' <bmod>}
<bmod> -> <bmul> {('%' <bmul>}
<bmul> -> <bsub> {'*' <bsub>}
<bsub> -> <badd> {'-' <badd>}
<badd> -> <bnot> {'+' <bnot>}
<bnot> -> [!]<bfac>
<bfac> -> 'id' | 'int_lit' | 'bool_lit' | '(' <bexpr> ')'

c. LL Gramar?

Grammar conforms to LL grammar standards:

1. Grammar holds no left-hand recursion
   
2. Grammar passes pairwise disjointness test:
   FIRST(program) = {start}
   FIRST(stmt_list) = {num, id, ?, O}
   FIRST(stmt) = {num}{id}{?}{O}
   FIRST(declare) = {num}
   FIRST(assign) = {id}
   FIRST(if) = {?}
   FIRST(loop) = {O}
   FIRST(expr) = {id, int_lit, (}
   FIRST(div) = {id, int_lit, (}
   FIRST(mod) = {id, int_lit, (}
   FIRST(mul) = {id, int_lit, (}
   FIRST(sub) = {id, int_lit, (}
   FIRST(add) {id, int_lit, (}
   FIRST(fac) = {id}{int_lit}{(}
   FIRST(bool_expr) = {!, id, int_lit, bool_lit, (}
   FIRST(bequal) = {!, id, int_lit, bool_lit, (}
   FIRST(brel) = {!, id, int_lit, bool_lit, (}
   FIRST(bexpr) = {!, id, int_lit, bool_lit, (}
   FIRST(bdiv) = {!, id, int_lit, bool_lit, (}
   FIRST(bmod) = {!, id, int_lit, bool_lit, (}
   FIRST(bmul) = {!, id, int_lit, bool_lit, (}
   FIRST(bsub) = {!, id, int_lit, bool_lit, (}
   FIRST(badd) = {!, id, int_lit, bool_lit, (}
   FIRST(bnot) = {!, id, int_lit, bool_lit, (}
   FIRST(bfac) = {id}{int_lit}{bool_lit}{(}
   

d. Ambiguous?

Grammar rules produce a non-ambiguous grammar

e-f. Lexical and Syntax Analysis

see code in src

g. Test Code

see files in testCode folder

code1.txt - valid code

code2.txt - valid code

code3.txt - lexical errors

line 2 - "numb" is not a keyword and starts with a letter so it will be treated as a identifier. "numb" does not match the criteria of a valid identifier, causing an error.
line 3 - "<--" is an unknown token and cannot be treated as a identifier or integer literal, causing an error.
line 4 - "true" is not a valid boolean_literal. A valid boolean_literal starts with a capital letter (True).
line 5 - "asdf" is not a valid identifier, causing an error.
line 7 - "stoop" is not the valid stop keyword. Will be treated as an identifier but does not match that criteria, causing an error.

code4.txt - syntax errors

line 2 - No opening bracket on the if statement, causing an error.
line 4 - Assigning "True" to a identifier. This is not allowed, causing an error.
line 6 - Two valid identifiers next to eachother. Does not make sense in this language, causing an error.
line 7 - Assigning the 'or' token to a identifier. This is not valid, causing an error.
line 7 - Missing semicolon, causing an error.

h. LR Trace

LR trace for:

start ? bool_lit { num id ; } ; stop

Accepted Trace (No Errors)

start num id ; id <- int_lit ; stop

Accepted Trace (No Errors)

start num id ; id = int_lit ; stop

Error on Trace (using "=" instead of "<-")

start ? bool_lit { ; stop

Error on Trace (unclosed selection statement)