Ocamlyacc Tutorial

Ocamlyacc Adaptation: SooHyoung Oh

This is a tutorial on how to use ocamlyacc which is distributed with Ocaml language.

Lots of part of this document are borrowed from the bison manual.

All license term in this document is NOT related with ocamlyacc; it is ONLY for this document.

Please mail all comments and suggestions to

This tutorial is work-in-progress. The latest version can be found at http://pllab.kaist.ac.kr/~shoh/ocaml/ocamllex-ocamlyacc/ocamlyacc-tutorial/index.html.

The companion tutorial for ocamllex is available at http://pllab.kaist.ac.kr/~shoh/ocaml/ocamllex-ocamlyacc/ocamllex-tutorial/index.html.

You can find the source of this document in ocamlyacc-tutorial-src.tar.gz. For who wants the other form, pdf (A4 size) for printing and html (tar.gz) are presented.

The source of the examples used in this document can be found ocamlyacc-examples.tar.gz.

Last updated: 2004-11-16

Table of Contents
1. Introduction
2. The Concepts of Ocamlyacc
2.1. Languages and Context-Free Grammars
2.2. From Formal Rules to Ocamlyacc Input
2.3. Semantic Values
2.4. Semantic Actions
2.5. Locations
2.6. Ocamlyacc Output: the Parser File
2.7. Stages in Using Ocamlyacc
2.8. The Overall Layout of a Ocamlyacc Grammar
3. Examples
3.1. Reverse Polish Notation Calculator
3.1.1. Declarations for "rpcalc"
3.1.2. Grammar Rules for rpcalc
3.1.3. The rpcalc Lexical Analyzer
3.1.4. The Controlling Function
3.1.5. The Error Reporting Routine
3.1.6. Running Ocamlyacc to Make the Parser
3.1.7. Compiling the Parser File
3.2. Infix Notation Calculator: calc
3.3. Simple Error Recovery
3.4. Location Tracking Calculator: ltcalc
3.4.1. Declarations for ltcalc
3.4.2. Grammar Rules for ltcalc
3.4.3. The "ltcalc" Lexical Analyzer
3.5. Multi-Function Calculator: mfcalc
3.5.1. Declarations for mfcalc
3.5.2. Grammar Rules for mfcalc
3.5.3. The mfcalc Symbol Table
4. Ocamlyacc Grammar Files
4.1. Outline of a Ocamlyacc Grammar
4.1.1. The Header Section
4.1.2. The Ocamlyacc Declarations Section
4.1.3. The Grammar Rules Section
4.1.4. The Trailer Section
4.2. Symbols, Terminal and Nonterminal
4.3. Syntax of Grammar Rules
4.4. Recursive Rules
4.5. Defining Language Semantics
4.5.1. Data Types of Semantic Values
4.5.2. Actions
4.6. Tracking Locations
4.6.1. Data Type of Locations
4.6.2. Actions and Locations
4.7. Ocamlyacc Declarations
4.7.1. Token Type Names
4.7.2. Operator Precedence
4.7.3. Nonterminal Symbols
4.7.4. The Start-Symbol
4.7.5. Ocamlyacc Declaration Summary
5. Parser Interface
5.1. The Parser Function
5.2. The Lexical Analyzer Function
5.3. The Error Reporting Function
6. The Ocamlyacc Parser Algorithm
6.1. Look-Ahead Tokens
6.2. Shift/Reduce Conflicts
6.3. Operator Precedence
6.3.1. When Precedence is Needed
6.3.2. Specifying Operator Precedence
6.3.3. Precedence Examples
6.3.4. How Precedence Works
6.4. Context-Dependent Precedence
6.5. Parser States
6.6. Reduce/Reduce Conflicts
6.7. Mysterious Reduce/Reduce Conflicts
7. Error Recovery
8. Debugging Your Parser
9. Invoking Ocamlyacc
9.1. Ocamlyacc Options
10. License of This Document
10.1. Bison License
10.1.1. License of bison manual
10.1.2. Conditions for Using Bison
10.1.3. Copying This Manual
10.1.4. GNU General Public License
10.2. Ocamlyacc Adaptation Copyright and Permissions Notice