Karel-Lite Lexer & Parser

A Java 17 implementation of a lexer and LL(1) recursive-descent parser for a minimal Karel-style language. Validates source programs against a context-free grammar, enforces static-scope rules, and reports success or failure.

Repository Layout

.
├── grammar.txt            ← EBNF-style grammar specification
├── source1.txt            ← Sample program
└── src
└── main
└── java
└── co
└── edu
└── uniandes
├── lexer      ← DFA-based tokenizer
└── parser     ← LL(1) recursive-descent parser

Grammar

See grammar.txt for the full grammar. Terminals include:

• Keywords: defvar, defun, if, loop, repeat, not
• Commands: move, jump, turn, face, move-dir, move-face, run-dirs, put, pick, null
• Directions: left, right, around, north, south, east, west, front, back
• Predicates: facing?, blocked?, can-move?, can-put?, can-pick?, isZero?
• Constants & identifiers: regex-matched names, numbers, and defined constants (Dim, Spaces, etc.)

Non-terminals and selection sets are embedded in Parser.java.

Build & Run

No external dependencies other than Java 17.

# Compile all sources
javac -source 17 -target 17 \
  $(find src/main/java -name '*.java')

# Run parser on sample program
java -cp src/main/java co.edu.uniandes.main.Main

Output:

• YES. on successful parse
• NO. <error message> on failure (lexical, syntactic, or scope error)

Lexer

• Class: co.edu.uniandes.main.lexer.Lexer

• Design:

  1. Builds a list of Rule(TokenType, Pattern) entries.
  2. Streams characters through a three-state DFA (START, MATCH, PARTIAL_MATCH).
  3. Emits maximal-munch tokens; whitespace is consumed by a separator rule.

Parser

• Class: co.edu.uniandes.main.parser.Parser

• Mechanism:

  • Recursive-descent methods (parseP, parseIs, parseI, etc.)
  • Static FIRST sets defined as SELECTION_SET_* constants
  • Scope tracking via a LinkedList<Scope> for variables and function signatures
  • Throws Exception with precise diagnostics on unexpected tokens or undefined identifiers