Coursify

Short Notes: YACC

Short Notes: YACC

Verified Sources
Sep 12, 2026

YACC (or “yacc”) is a Unix parser generator that produces an efficient ((LALR(1))) parser from a grammar written in a notation similar to Backus–Naur Form (BNF).
It is used to recognize whether an input token stream conforms to a specified context-free grammar and to execute user-defined semantic actions during reductions.

Key ideas:

  • YACC accepts a grammar file containing token and grammar declarations plus C code actions.
  • The generated parser calls a lexer routine (commonly yylex), and reports errors via yyerror.
  • YACC uses LALR(1) parsing (a variant of LR parsing that remains practical by using smaller parsing tables).2

Mermaid overview of the pipeline:

Footnotes

  1. Yacc - Wikipedia - Describes Yacc as an LALR parser generator using BNF-like grammar notation. ↩ ↩2

  2. Introduction to YACC - GeeksforGeeks - Summarizes YACC grammar specification and semantic actions; notes typical file parts. ↩ ↩2

  3. Lex and YACC primer/HOWTO (lex-yacc internal interface) - Explains yylex() returns token type and puts values in yylval. ↩

  4. Yacc/Bison - Parser Generators - Part 1 (Linux Gazette #87) - Explains Yacc as LALR(1) and discusses reasons tables are smaller than LR. ↩

How YACC is used (conceptual lifecycle)

Define tokens & productions

1) Write grammar file

Specify terminals/non-terminals and the grammar rules; attach actions to rules."

Generate parser code

2) Run yacc on the grammar

YACC produces C source implementing a shift/reduce LALR(1)LALR(1) parser."

Build executable

3) Compile & link

Compile generated parser with your lexer and support code."

Execute yyparse()

4) Parse inputs

yyparse() repeatedly reads tokens from yylex(); semantic actions run during reductions."

Grammar file structure (what you write)

A typical YACC input is conceptually split into three parts:

  1. Definitions / declarations (tokens, types, prologue code)
  2. Grammar rules (the BNF-like productions with actions)
  3. Auxiliary routines (e.g., implementations for yyerroryyerror or other helper functions)

This “definitions %% rules %% auxiliary routines” structure is commonly described in tutorials and references.

Short note: YACC translates the grammar into a C parser; the actions you write determine what computations happen as the parse proceeds.

Footnotes

  1. Introduction to YACC - GeeksforGeeks - Summarizes YACC grammar specification and semantic actions; notes typical file parts. ↩ ↩2

How semantic actions work with $$$, $1, $2, \dots$

  1. 1
    Step 1

    In a rule like A : B C { ... } ;, the code block is run when that production is reduced.

  2. 2
    Step 2

    YACC typically uses $$ as the return value for the left-hand side (the reduced nonterminal). For example, { $$ = 1; } returns 1 for that rule.

    Footnotes

    1. Yacc Yet Another Compiler Compiler by Stephen C. Johnson (UT Austin mirror) - Defines $$ and $1, $2, ... semantic action variables and mid-rule control. ↩

  3. 3
    Step 3

    Within the action, $1, $2, ... refer to semantic values returned by the grammar symbols on the rule’s RHS from left to right.

    Footnotes

    1. Yacc Yet Another Compiler Compiler by Stephen C. Johnson (UT Austin mirror) - Defines $$ and $1, $2, ... semantic action variables and mid-rule control. ↩

  4. 4
    Step 4

    If no explicit action is given for a rule, a common default is $$ = $1 (the value of the first RHS symbol).

    Footnotes

    1. yacc manpage / POSIX-style description (OpenGroup) - Documents action placement and how actions/mid-rule actions work; includes default action behavior details. ↩

  5. 5
    Step 5

    Actions can appear in the middle of a rule, not only at the end; this affects when values are computed and can introduce conflicts.

    Footnotes

    1. yacc manpage / POSIX-style description (OpenGroup) - Documents action placement and how actions/mid-rule actions work; includes default action behavior details. ↩

Precedence and associativity (resolving shift/reduce conflicts)

YACC can resolve ambiguous cases using precedence and associativity declarations such as %left, %right, %nonassoc.2

Important points:

  • Each grammar rule gets a precedence and associativity associated with the last token/literal in its body, unless overridden by %prec.2
  • If a conflict occurs and the involved token and rule have precedence/associativity, the parser selects the action (shift vs reduce) based on higher precedence; if equal, associativity decides (left implies reduce; right implies shift; nonassoc implies an error).2
  • The %prec keyword can override rule precedence by assigning the rule the precedence of a specified token/literal.

Footnotes

  1. Precedence (Oracle docs mirror) - Describes precedence/associativity conflict resolution rules. ↩ ↩2 ↩3

  2. yacc (POSIX / OpenGroup utility description) - Explains precedence/associativity attached to last token and %prec override. ↩ ↩2 ↩3 ↩4

Pro Tip

When you’re dealing with expression grammars (e.g., +, -, *, /), declare operator precedence using %left/%right and use %prec when unary/binary operators need different binding strengths. Precedence is attached to the last token in the rule by default.

Footnotes

  1. yacc (POSIX / OpenGroup utility description) - Explains precedence/associativity attached to last token and %prec override. ↩

Warning

If you insert mid-rule actions, you may change the grammar’s structure (effectively introducing a new nonterminal in the underlying transformation), which can create conflicts that wouldn’t otherwise exist.

Footnotes

  1. yacc manpage / POSIX-style description (OpenGroup) - Documents action placement and how actions/mid-rule actions work; includes default action behavior details. ↩

YACC interface with a lexer (tokens and semantic values)

In the classic lex+yacc model:

  • The parser calls yyparse.
  • yyparse repeatedly calls the lexer function **yylex to get the next token type.
  • The lexer may also provide a semantic value in yylval, which YACC uses inside semantic actions.

A key contract:

  • yylex() returns an integer token type; the token’s attribute is placed into yylval.
  • By default, yylval is of type int, unless you override it (e.g., via YYSTYPE in traditional setups).

Footnotes

  1. Lex and YACC primer/HOWTO (lex-yacc internal interface) - Explains yylex() returns token type and puts values in yylval. ↩ ↩2 ↩3 ↩4

YACC vs. modern equivalents (short note)

Historically, YACC is a classic LALR(1) parser generator; modern systems often use GNU Bison, which is “Yacc-compatible” and typically defaults to producing LALR(1) parsers (but can also generate other parser types).

Concept mapping: YACC responsibilities

A quick “what does which part do” view

Quick short notes (exam-style)

Knowledge Check

Question 1 of 4
Q1Single choice

In a YACC action attached to a production, $$ refers to:

Explore Related Topics

1

Understanding Digital Counters: Principles, Types, and Applications

Digital counters are sequential circuits built from cascaded flip‑flops that count input events, with a maximum modulus of 2ᴺ for N stages, and are classified as asynchronous (ripple) or synchronous based on clock distribution.

  • Asynchronous counters cascade flip‑flop clocks, causing cumulative propagation delay and limiting maximum frequency.
  • Synchronous counters receive the clock simultaneously, using combinational logic to eliminate ripple delay and support higher speeds.
  • Designing a synchronous Mod‑6 counter involves defining the state sequence, creating excitation tables, simplifying with Karnaugh maps, and wiring JK flip‑flops with derived logic.
  • Ring counters yield N states; Johnson counters double this to 2N states.
  • Prevent glitches and lock‑out by using Gray‑code sequencing, output strobes, and ensuring unused states redirect to the main count sequence.
2

Topological Sorting (Write Short Notes)

3

Activation Record: Short Notes (Stack Frames in Procedure Calls)

Browse all research articles