LARA

Lecture 05: LR Parsing

Continuing Lecture 04, Lecture 03

Announcement: projects updated, include Earley parser

Introduction

Pushdown Automata

LL Parser uses Leftmost Derivation

LR Parser uses Rightmost Derivation

LR Parser Runs Automaton over Stack

LR Parser without Lookahead

Automata for LR Parsing without Lookahead

LR(0) Parser Actions

SLR Parser Actions

LR Parser with Lookahead

LR Parsing with Lookahead Items

LR(1) Parser Actions

LR Parsing Tables

Precedence

Precedence in LR Parsing

Tools

Traditional, widely used, tool is called yacc (for Yet Another Compiler Compiler) developed for C.

Its versions are available for Java (called 'CUP'), OCaml (ocamlyacc), and other languages.

Example ocamlyacc grammar

Grammar of Formulas in CUP

Reference

Discussion of Semantic Analysis

Examples of semantic analysis:

  • undeclared identifiers
  • duplicate identifiers in same scope
  • variables read but not written / written but not read / not used
  • type mismatch for built-in operators (if (7) …)
  • calling unknown methods, accessing unknown fields
  • variables read before being written
  • unreachable code
  • accessing variable out of bounds