This is a homework assignment so I'm only looking to get unstuck. We are tasked with filling out a parser and lexical analyzer. This was going fine until I ran into an issue reading ";".
As a result I am unable to continue making progress.
Using Dr Racket I would like help passing example5
the error parse-small-lang: error occurred, #t 'SEMI #f
#lang racket
;; Author: Redacted
;; Import the parser and lexer generators.
(require parser-tools/lex
parser-tools/yacc
(prefix-in : parser-tools/lex-sre))
(define-tokens value-tokens (NUM ID))
(define-empty-tokens op-tokens
(CLASS
EXTENDS
METHOD
IF
THEN
ELSE
NEW
SUPER
FIELD
BSLASH
ARROW
PROCS
BEGIN
END
SEND
SEMI
EQ2
OP
CP
COMMA
EQ1
LET
IN
+
-
*
/
EOF))
(define-lex-abbrevs
(lower-letter (:/ "a" "z"))
(upper-letter (:/ "A" "Z"))
(letter (:or lower-letter upper-letter))
(digit (:/ "0" "9"))
(ident (:+ idfirst (:* idrest)))
(idfirst (:or letter "_" "$"))
(idrest (:or idfirst digit))
(digits (:* digit))
(number
(:+ digits
(:? "." digits)
(:?(:or "e" "E") (:? (:or "+" "-"))) digits)))
;get-token: inputPort -> token
(define get-token
(lexer
((eof) 'EOF)
("class" 'CLASS)
("method" 'METHOD)
("extends" 'IF)
("then" 'THEN)
("else" 'ELSE)
("new" 'NEW)
("super" 'SUPER)
("field" 'FIELD)
("let" 'LET)
("in" 'IN)
("\\" 'BSLASH)
("->" 'ARROW)
("procedures" 'PROCS)
("{" 'BEGIN)
("}" 'END)
("(" 'OP)
(")" 'CP)
("." 'SEND)
(";" 'SEMI)
("," 'COMMA)
("=" 'EQ1)
("==" 'EQ2)
("+" '+)
("-" '-)
("*" '*)
("/" '/)
((:: digits (:? (:: "." digits)) (:? (:: (:or "E" "e") (:? (:or "+" "-")) digits)))
(token-NUM (string->number lexeme)))
(ident (token-ID (string->symbol lexeme)))
(whitespace (get-token input-port))))
;;; data definitions
;; A small language expression (SmallLangExp) is one of the following.
;; a number n
;; an identifier x
;; a sum with parts e1 and e2,
;; where e1 and e2 are small language expressions
;; a difference with parts e1 and e2,
;; where e1 and e2 are small language expressions
;; a product with parts e1 and e2,
;; where e1 and e2 are small language expressions
;; a quotient with parts e1 and e2,
;; where e1 and e2 are small language expressions
;; a negation with part e,
;; where e is an small language expression
;; a bindings with parts defs and e,
;; where defs is a list of identifiers * SmallLangExp
;; and e is an small language expression
;; functions for associated with each part: predicate, constructor, selectors.
;; Number is a Scheme number
;; Identifier is a Scheme symbol
; make-sum: SmallLangExp * SmallLangExp -> SumExp
(define (make-sum exp1 exp2)
(list 'sum exp1 exp2))
(equal? (make-sum 2 3) '(sum 2 3))
; make-diff: SmallLangExp * SmallLangExp -> DiffExp
(define (make-diff exp1 exp2)
(list 'diff exp1 exp2))
(equal? (make-diff 2 3) '(diff 2 3))
; make-prod: SmallLangExp * SmallLangExp -> ProdExp
(define (make-prod exp1 exp2)
(list 'prod exp1 exp2))
(equal? (make-prod 2 3) '(prod 2 3))
; make-quo: SmallLangExp * SmallLangExp -> QuoExp
(define (make-quo exp1 exp2)
(list 'quo exp1 exp2))
(equal? (make-quo 2 3) '(quo 2 3))
; make-neg: SmallLangExp -> NegExp
(define (make-neg exp)
(list 'neg exp))
(equal? (make-neg 2) '(neg 2))
; make-let: Listof(Identifier*SmallLangExp) * SmallLangExp -> BindingExp
; Identifier*SmallLangExp is represented as a two element list
(define (make-let defs exp)
(list 'with-bindings defs exp))
(equal? (make-let (list (list 'x 1) (list 'y 2)) 3) '(with-bindings ((x 1) (y 2)) 3))
;; constructors
; make-program
(define (make-program e1 e2) (list 'program e1 e2))
; make-class
(define (make-class e1 e2 e3 e4) (list 'class e1 e2 e3 e4))
; make-method
(define (make-method e1 e2 e3) (list 'method e1 e2 e3))
; make-new
(define (make-new e1 e2) (list 'new e1 e2))
; make-supercall
(define (make-supercall e1 e2) (list 'super e1 e2))
; make-seq
(define (make-seq e1) (list 'sequence e1))
; make-procs
(define (make-procs e1 e2) (list 'procedures e1 e2))
; make-if
(define (make-if e1 e2 e3) (list 'if e1 e2 e3))
; make-assign
(define (make-assign e1 e2) (list 'assign! e1 e2))
;(equal? (make-assign 'x 3) '(assign! x 3))
; make-equal
(define (make-equal e1 e2) (list 'equality? e1 e2))
; make-proc
(define (make-proc e1 e2) (list 'proc e1 e2))
; make-access
(define (make-access e1 e2) (list 'send e1 e2))
; make-funcall
(define (make-funcall e1 e2) (list 'funcall e1 e2))
; parse-small-lang: (() -> token) -> SmallLangExp
(define parse-small-lang
(parser
(start program)
(end EOF)
(tokens value-tokens op-tokens)
(error (lambda (a b c) (error 'parse-small-lang "error occurred, ~v ~v ~v " a b c )))
(grammar
(program ((class-decs exp) (make-program $1 $2)))
(class-decs (() null)
((class-dec class-decs) (cons $1 $2)))
(class-dec ((CLASS ID EXTENDS ID BEGIN field-dec meth-dec END) (make-class $2 $4 $6 $7)))
(field-dec (() null)
((FIELD ID field-dec) (cons $2 $3)))
(meth-dec ((METHOD ID OP formals CP exp meth-dec) (cons(make-method $2 $4 $6) $7))
(() null))
(exp ((LET let-defs IN exp) (make-let $2 $4))
((PROCS proc-defs IN exp) (make-procs $2 $4))
((BEGIN exp END) (make-seq $2))
((IF exp THEN exp ELSE exp)(make-if $2 $4 $6))
((BSLASH formals BSLASH ARROW exp) (make-proc $2 $5))
((NEW ID OP actuals CP) (make-new $2 $4))
((SUPER ID OP actuals CP) (make-supercall $2 $4))
((ID EQ1 exp) (make-assign $1 $3))
((comp-exp) $1))
(let-def ((ID EQ1 exp) (list $1 $3)))
(let-defs ((let-def) (list $1))
((let-def COMMA let-defs) (cons $1 $3)))
(proc-def ((ID OP formals CP EQ1 exp) (list $1 (make-proc $3 $6))))
(proc-defs ((proc-def) (list $1))
((proc-def COMMA proc-def) (cons $1 $3)))
(exps ((exp) (list $1))
((exp SEMI exps) (cons $1 $3)))
(comp-exp ((math-exp EQ2 math-exp) (make-equal $1 $3))
((math-exp) $1))
(math-exp ((math-exp + term) (make-sum $1 $3))
((math-exp - term) (make-diff $1 $3))
((term) $1))
(term ((term * factor) (make-prod $1 $3))
((term / factor) (make-quo $1 $3))
((factor) $1))
(factor ((simple) $1)
((NUM) $1)
((- factor) (make-neg $2)))
(simple ((ID) $1)
((simple SEND ID) (make-access $1 $3))
((simple OP actuals CP) (make-funcall $1 $3))
((OP exp CP) $2))
(actuals (() null)
((actualsNE) $1))
(actualsNE ((exp) (list $1))
((exp COMMA actualsNE) (cons $1 $3)))
(formals (() null)
((formalsNE) $1))
(formalsNE ((ID) (list $1))
((ID COMMA formalsNE) (cons $1 $3)))
)))
; lexer/parser test
(define (tokens<-string str)
(let ((i (open-input-string str)))
(let loop ((result '())
(tok (get-token i)))
(if (eq? tok 'EOF)
(reverse result)
(loop (cons tok result) (get-token i))))))
(define (ast<-string str)
(let ((i (open-input-string str)))
(parse-small-lang (lambda () (get-token i)))))
(let ((example "let x = -2 + 3 * 4, y = 0 in -2+5*x+y"))
(equal? (ast<-string example)
'(program () (with-bindings ((x (sum (neg 2) (prod 3 4)))
(y 0))
(sum (sum (neg 2) (prod 5 x)) y)))))
;; Predicates
; sum?: Any -> Bool
(define (sum? a) (and (pair? a) (eq? (car a) 'sum)))
; difference?: Any -> Bool
(define (difference? a) (and (pair? a) (eq? (car a) 'diff)))
; product?: Any -> Bool
(define (product? a) (and (pair? a) (eq? (car a) 'prod)))
; quotient?: Any -> Bool
(define (quotient? a) (and (pair? a) (eq? (car a) 'quo)))
; neg?: Any -> Bool
(define (negate? a) (and (pair? a) (eq? (car a) 'neg)))
; let? Any -> Bool
(define (let? expr)
(and (pair? expr)
(= (length expr) 2)
(pair? (car expr))))
;; Selectors
; arg1: MathExp -> SmallLangExp
(define (arg1 e) (car (cdr e)))
; arg2: MathExp -> SmallLangExp
(define (arg2 e) (car (cdr (cdr e))))
; neg-exp: NegExp -> SmallLangExp
(define (neg-exp e) (car(cdr e)))
; let-defs: BindingExp -> Listof(Identifier*SmallLangExp)
(define (let-defs e) (car e))
; let-exp: BindingExp -> SmallLangExp
(define (let-exp e) (cdr e))
;; large language definitions
;; large language expression structure
;; large language method structure
;; large language class structure
;; null
;; an extension with parts e1, e2, e3, e4
;; where e1 and e2 are identifiers
;; e3 is a field declaration
;; and e4 is a method declaration
;; large language program structure
;; a program with parts e1 and e2,
;; where e1 is a class declaration
;; and e2 is a large language expression
; program? Any -> Bool
(define (program? a) (eq? (car a) 'program))
; class-decl? Any -> Bool
(define (class-decl? a) (eq? (car a) 'class))
; method? Any -> Bool
;(method e1 e2 e3)
; e1 identity, e2 formals, e3 expression
(define (method? a) (eq? (car a) 'method))
; new? Any -> Bool
(define (new? a) (eq? (car a) 'new))
; supercall? Any -> Bool super
(define (supercall? a) (eq? (car a) 'super))
; seq? Any -> Bool sequence
(define (seq? a) (eq? (car a) 'sequence))
; procs? Any -> Bool procs
(define (procs? a) (eq? (car a) 'procs))
; if? Any -> Bool if
(define (if? a) (eq? (car a) 'if))
; assign? Any -> Bool assign
(define (assign? a) (eq? (car a) 'assign))
; equality? Any -> Bool equal
(define (equality? a) (eq? (car a) 'equal))
; proc? Any -> Bool proc
(define (proc? a) (eq? (car a) 'proc))
; access? Any -> Bool access
(define (access? a) (eq? (car a) 'access))
; funcall? Any -> Bool funcall
(define (funcall? a) (eq? (car a) 'funcall))
; selectors
; program-decls
(define (program-decls p) (car (cdr p)))
; program-exp
(define (program-exp p) (cdr (cdr p)))
; class-name
(define (class-name c) (car (cdr c)))
; class-parent
(define (class-parent c) (car (cdr (cdr c))))
; class-fields
(define (class-fields c) (car (cdr (cdr (cdr c)))))
; class-methods
(define (class-methods c) (cdr (cdr (cdr (cdr c)))))
; method-name
(define (method-name m) (car (cdr m)))
; method-formals
(define (method-formals m) (car (cdr (cdr m))))
; method-exp
(define (method-exp m) (cdr (cdr (cdr m))))
; new-name
(define (new-name n) (car (cdr n)))
; new-rands
(define (new-rands n) (cdr (cdr n)))
; supercall-name
(define (supercall-name s) (car (cdr s)))
; supercall-rands
(define (supercall-rands s) (cdr (cdr s)))
; seq-exps
(define (seq-exps s) (cdr s))
; procs-defs
(define (procs-defs p) (car (cdr p)))
; procs-exp
(define (procs-exp p) (cdr (cdr p)))
; if-exp1
(define (if-exp1 i) (car (cdr i)))
; if-exp2
(define (if-exp2 i) (car (cdr (cdr i))))
; if-exp3
(define (if-exp3 i) (cdr (cdr (cdr i))))
; assign-var
(define (assign-var a) (car (cdr a)))
; assign-exp
(define (assign-exp a) (cdr (cdr a)))
; proc-formals
(define (proc-formals p) (car (cdr p)))
; proc-exp
(define (proc-exp p) (cdr (cdr p)))
; access-exp
(define (access-exp a) (car (cdr a)))
; access-message
(define (access-message a) (cdr (cdr a)))
; funcall-rator
(define (funcall-rator f) (car (cdr f)))
; funcall-rands
(define (funcall-rands f) (cdr (cdr f)))
; tests
(define example1 "let x = -2 + 3 * 4, y = 0 in -2+5*x+y")
(define example2 "let x = -2 + 3.5 * 4, y = 0 in -2+5*x+y")
(define example3 "let x = -2 + 3e2 * 4, y = 0 in -2+5*x+y")
(define example4 "let _x = -2 + 3 * 4, $y2 = 0 in -2+5*x+y")
(define example5 "let x = -(1+1) + 3 * 4, y = 0 in {y = 14; x == y}")
(define example6
"let pred = \\k\\->k-1
in procedures f(n) = if n == 0
then 1
else n * f(pred(n))
in f(4+1)")
(define example7
"class point extends object{
field x
field y
method init(initx, inity){
x = initx;
y = inity
}
method move(dx, dy){
x = x + dx;
y = y + dy
}
}
let ob = new point(2+3, 1+4*7) in
ob.move(0.1,3)")
(equal? (ast<-string example1)
'(program ()
(with-bindings ((x (sum (neg 2) (prod 3 4)))
(y 0))
(sum (sum (neg 2) (prod 5 x)) y))))
(equal? (ast<-string example2)
'(program ()
(with-bindings ((x (sum (neg 2) (prod 3.5 4)))
(y 0))
(sum (sum (neg 2) (prod 5 x)) y))))
(equal? (ast<-string example3)
'(program ()
(with-bindings ((x (sum (neg 2) (prod 3e2 4)))
(y 0))
(sum (sum (neg 2) (prod 5 x)) y))))
(equal? (ast<-string example4)
'(program ()
(with-bindings ((_x (sum (neg 2) (prod 3 4)))
($y2 0))
(sum (sum (neg 2) (prod 5 x)) y))))
(equal? (ast<-string "-(1+1)") '(program () (neg (sum 1 1)))) ; neg sum
(equal? (ast<-string "let x = -(1+1) + 3 * 4, y = 0 in x") '(program () (with-bindings ((x (sum (neg (sum 1 1)) (prod 3 4))) (y 0)) x))) ; let
(equal? (ast<-string "{ 2 }") '(program () (sequence 2))) ; seq
(equal? (ast<-string "x == y")'(program () (equality? x y))) ; second eq2
(equal? (ast<-string "y = 14") '(program () (assign! y 14))) ; first assign
(equal? (ast<-string "y = 14; x == y") '(program () (assign! y 14) (equality? x y))) ; semi
(equal? (ast<-string "{y = 14; x == y}") '(program () (sequence (assign! y 14) (equality? x y)))) ; seq and semi
(equal? (ast<-string example5)
'(program
()
(with-bindings
((x (sum (neg (sum 1 1)) (prod 3 4))) (y 0))
(sequence (assign! y 14) (equality? x y)))))
;(equal? (ast<-string example6)
; '(program
; ()
; (with-bindings
; ((pred (proc (k) (diff k 1))))
; (procedures
; ((f
; (proc
; (n)
; (if (equality? n 0) 1 (prod n (funcall f (funcall pred n)))))))
; (funcall f (sum 4 1))))))
;(equal? (ast<-string example7)
; '(program
; ((class point object
; (x y)
; ((method
; init
; (initx inity)
; (sequence (assign! x initx) (assign! y inity)))
; (method
; move
; (dx dy)
; (sequence (assign! x (sum x dx)) (assign! y (sum y dy)))))))
; (with-bindings
; ((ob (new point (sum 2 3) (sum 1 (prod 4 7)))))
; (funcall (send ob move) 0.1 3))))
So far I have confirmed that my implementation of the grammar to the best of my ability:
program⟩ ::= ⟨classdecls⟩⟨expr ⟩ [program $1 $2]
⟨classdecls⟩ ::= ε [null]
⟨classdecls⟩ ::= ⟨classdecl⟩ ⟨classdecls⟩ [cons $1 $2]
⟨classdecl⟩ ::= class ident extends ident{ ⟨fielddecls⟩⟨methdecls⟩} [class $2 $4 $6 $7]
⟨fielddecls⟩ ::= ε [null]
⟨fielddecls⟩ ::= field ident ⟨fielddecls⟩ [cons $2 $3]
⟨methdecls⟩ ::= ε [null]
⟨methdecls⟩ ::= method ident ( ⟨formals⟩ )⟨expr ⟩ ⟨methdecls⟩ [cons (method $2 $4 $6) $7]
⟨expr ⟩ ::= let ⟨letdefs⟩ in ⟨expr ⟩ [let $2 $4]
⟨expr ⟩ ::= procedures ⟨procdefs⟩ in ⟨expr ⟩ [procs $2 $4]
⟨expr ⟩ ::= { ⟨exprs⟩ } [sequence $2]
⟨expr ⟩ ::= if ⟨expr ⟩ then ⟨expr ⟩ else ⟨expr ⟩ [if $2 $4 $6]
⟨expr ⟩ ::= \ ⟨formals⟩ \ -> ⟨expr ⟩ [proc $2 $5]
⟨expr ⟩ ::= new ident (⟨actuals⟩ ) [new $2 $4]
⟨expr ⟩ ::= super ident (⟨actuals⟩ ) [super $2 $4]
⟨expr ⟩ ::= ident = ⟨expr ⟩ [assign $1 $3]
⟨expr ⟩ ::= ⟨compexpr ⟩ [$1]
⟨letdefs⟩ ::= ⟨letdef ⟩ [list $1]
⟨letdefs⟩ ::= ⟨letdef ⟩ , ⟨letdefs⟩ [cons $1 $3]
⟨letdef ⟩ ::= ident = ⟨expr ⟩ [list $1 $3]
⟨procdefs⟩ ::= ⟨procdef ⟩ [list $1]
⟨procdefs⟩ ::= ⟨procdef ⟩ , ⟨procdefs⟩ [cons $1 $3]
⟨procdef ⟩ ::= ident ( ⟨formals⟩ ) = ⟨expr ⟩ [list $1 (proc $3 $6)]
⟨exprs⟩ ::= ⟨expr ⟩ [list $1]
⟨exprs⟩ ::= ⟨expr ⟩ ; ⟨exprs⟩ [cons $1 $3]
⟨compexpr ⟩ ::= ⟨mathexpr ⟩ == ⟨mathexpr ⟩ [equal $1 $3]
⟨compexpr ⟩ ::= ⟨mathexpr ⟩ [$1]
⟨mathexpr ⟩ ::= ⟨mathexpr ⟩ + ⟨term⟩ [sum $1 $3]
⟨mathexpr ⟩ ::= ⟨mathexpr ⟩ - ⟨term⟩ [diff $1 $3]
⟨mathexpr ⟩ ::= ⟨term⟩ [$1]
⟨term⟩ ::= ⟨term⟩ * ⟨factor ⟩ [prod $1 $3]
⟨term⟩ ::= ⟨term⟩ / ⟨factor ⟩ [quotient $1 $3]
⟨term⟩ ::= ⟨factor ⟩ [$1]
⟨factor ⟩ ::= ⟨simple⟩ [$1]
⟨factor ⟩ ::= number [$1]
⟨factor ⟩ ::= - ⟨factor ⟩ [negate $2]
⟨simple⟩ ::= ident [$1]
⟨simple⟩ ::= ⟨simple⟩ . ident [access $1 $3]
⟨simple⟩ ::= ⟨simple⟩ ( ⟨actuals⟩ ) [funcall $1 $3]
⟨simple⟩ ::= ( ⟨expr ⟩ ) [$2]
⟨actuals⟩ ::= ε [null]
⟨actuals⟩ ::= ⟨nonemptyactuals⟩ [$1]
⟨nonemptyactuals⟩ ::= ⟨expr ⟩ [list $1]
⟨nonemptyactuals⟩ ::= ⟨expr ⟩ , ⟨nonemptyactuals⟩ [cons $1 $3]
⟨formals⟩ ::= ε [null]
⟨formals⟩ ::= ⟨nonemptyformals⟩ [$1]
⟨nonemptyformals⟩ ::= ident [list $1]
⟨nonemptyformals⟩ ::= ident , ⟨nonemptyformals⟩ [cons $1 $3]
as well as writing some additional tests to confirm (i think) that my issue has to do with the semi-colon token 'SEMI
As @user207421 hinted, I think you're confused about the source of the error. DrRacket indicates that program "y = 14; x == y" is the one causing the "SEMI" error. In your grammar, SEMI appears to be valid only within BEGIN and END, so it makes sense that this one gives you an error.
To get example5 passing, try changing
(BEGIN exp END) to (BEGIN exps END), and
(define (make-seq e1) (list 'sequence e1)) to (define (make-seq exps) (cons 'sequence exps))