Designing Grammar Rules for a Mini C Language Compiler

Designing Grammar Rules for a Mini C Language Compiler —— 02 Grammar Rule Design

Overview of Grammar

The MiniC grammar adopts the syntax rules of Antlr4, divided into two main parts: lexical rules (Lexer Rules) and syntax rules (Parser Rules). The lexical rules are the rules for constructing words in the language, responsible for converting the source code character stream into meaningful lexical units (Tokens). The syntax rules describe the rules for sentences in the language, defining how these Tokens combine into valid program structures.

Antlr4 Grammar Rules

Basic Structure

A complete <span>.g4</span> file typically contains five parts (in order):Grammar Declaration → Options Configuration → Token Declaration → Lexical Rules → Syntax Rules

// 1. Grammar Declaration (mandatory)
grammar MiniC;  // Define parser grammar, file name must be MiniC.g4 (since Antlr is written in Java)

// 2. Options Configuration (optional, can also be specified at compile time on the command line)
options {
    language = Cpp;  // Generate C++ code (default is Java, also supports C#, Python, and other target languages)
    tokenVocab = MiniCLexer;  // Reference external lexical rules (when lexical/syntax are defined in two separate files)
}

// 3. Token Declaration (optional, used to reference tokens not defined in the current file)
tokens {
    LBRACE, RBRACE  // Declare brace tokens (must be defined in lexical rules)
}

// 4. Lexical Rules (define tokens, starting with uppercase)
INT : [0-9]+ ;
ID  : [a-zA-Z_][a-zA-Z0-9_]* ;
OP_ADD: '+';
OP_SUB: '-';
OP_MUL: '*';
OP_DIV: '/';
OP_ASSIGN: '=';

// 5. Syntax Rules (define syntax structures, starting with lowercase)
assign: ID '=' expr;
expr: addExpr;
addExpr: mulExpr (addOp mulExpr)*;
addOp: OP_ADD | OP_SUB;
mulExpr: primary (mulOp primary)*;
mulOp: OP_MUL | OP_DIV;
primary: INT | ID | LPAREN expr RPAREN;

/*
For parsing a = 5 * 2 + 9 * 4:

                 a
                 |
                 =
                 |
                 +
               /   \
             *      *
            / \    /  \
           5   2   9   4

The result can be correctly calculated without parentheses, as the operator precedence is already hidden in the order of syntax rules.
*/

Lexical Rules

Define how to break down the input character stream into tokens (such as keywords, identifiers, operators),the rule names must start with uppercase letters, and the core is the “regular expression style matching pattern”.

Basic Format

RuleName : MatchingPattern ( -> Action )? ;

Common Matching Patterns (similar to regular expressions)

Pattern Element Description Example
<span>[CharacterSet]</span> Matches any character in the character set <span>DIGIT : [0-9] ;</span> (matches a single digit)
<span>[^CharacterSet]</span> Matches any character not in the character set <span>NON_ZERO : [1-9] ;</span> (matches non-zero digits)
`A B` Matches A or B (branch selection)
<span>A*</span> Matches A zero or more times (greedy mode) <span>INT : DIGIT+ ;</span> (matches one or more digits)
<span>A+</span> Matches A one or more times <span>STRING : '"' .*? '"' ;</span> (matches strings, <span>.*?</span> non-greedy matches any character until the next <span>"</span>)
<span>A?</span> Matches A zero or one time `SIGNED_INT : (‘+’
<span>A.B</span> Matches A followed by B (sequential concatenation) <span>ASSIGN : '=' ;</span> (matches the assignment operator)
<span>'String'</span> Matches a fixed string (literal) <span>IF : 'if' ;</span> (matches the keyword if)
<span>.</span> Matches any single character (except newline) <span>ANY : . ;</span> (matches any character)
<span>~'x'</span> Matches any character except ‘x’ <span>NOT_X : ~'x' ;</span>

Special Actions

Process matched tokens through <span>-> Action</span> (such as skip, hide, pass to a specific channel).

Action Description Example
<span>skip</span> Skips the current matched content (does not generate a token) <span>WS : [ \t\n\r]+ -> skip ;</span> (skips whitespace)
<span>channel(ChannelName)</span> Puts the token into the specified channel (default channel is <span>DEFAULT_TOKEN_CHANNEL</span>, hidden channel <span>HIDDEN</span> does not participate in syntax parsing) <span>COMMENT : '//' .*? '\n' -> channel(HIDDEN) ;</span> (puts comments into the hidden channel)
<span>type(TokenName)</span> Forces the matched content to be marked as the specified token type <span>ID : [a-zA-Z]+ ; 'if' -> type(IF) ;</span> (marks “if” as IF instead of ID)

Fragments

Define auxiliary patterns used only for other lexical rules with <span>fragment</span>, not generating independent tokens, used to simplify rule reuse.

Example:

// Define digit fragment (does not generate token)
fragment DIGIT : [0-9] ;
fragment LETTER : [a-zA-Z] ;

// Reuse fragment to define token
INT : DIGIT+ ;  // Integer = one or more digits
ID  : LETTER (LETTER | DIGIT)* ;  // Identifier = starts with a letter, followed by letters/numbers

Lexical Rule Priority

  • Order Priority: When multiple lexical rules can match the input, the earlier rule takes precedence. For example, keywords must be defined before identifiers, otherwise they will be recognized as ID:
    // When the current token is "if", since the IF rule is before the ID rule, it will prioritize matching "if" as the IF keyword, not as an identifier
    IF : 'if' ;  // Prioritize matching "if" as the IF keyword
    ID : [a-zA-Z]+ ;  // Then match other letters as identifiers

5. Syntax Rules (Parser Rules)

Define the combination relationships between tokens (such as expressions, statements, function structures), describing the syntax structure of the target language,the rule names must start with lowercase letters.

Basic Format

RuleName : RuleBody ( -> Action )? ;

Elements of Rule Body

Element Description Example
<span>TokenName</span> References tokens defined in lexical rules <span>stmt : ID '=' expr ';' ;</span> (references ID, =, ; tokens)
<span>RuleName</span> References other syntax rules (nested structures) <span>expr : term '+' term ;</span> (references term rule)
`A B` Branch selection (matches A or B)
<span>A*</span>/<span>A+</span>/<span>A?</span> Quantifiers (0 times or more, 1 time or more, 0 times or 1 time) <span>block : '{' stmt* '}' ;</span> (code block contains 0 or more statements)
<span>(A B C)</span> Grouping (treats multiple elements as a whole) <span>expr : INT ( '+' INT )* ;</span> (an integer can be followed by 0 or more “+ integers”)
<span>A -> B</span> Semantic action (generating AST nodes, executing code, etc.) <span>expr : a=INT '+' b=INT -> ^(ADD $a $b) ;</span> (generates ADD node, child nodes are andb)
<span># Label</span> Names branches (used for accessor pattern to distinguish branches) `expr : expr ‘+’ expr # AddExpr
<span>$VariableName</span> References token variables in the rule (used for semantic actions) <span>a=INT '+' b=INT -> $a + $b</span> (references the token values matched by a and b)

Syntax Rule Priority and Ambiguity

  • Branch Order: The earlier branches in the rule body have higher priority, which can be used to resolve ambiguity (such as operator precedence). For example, let multiplication take precedence over addition:
    expr : term ( '+' term )* ;  // Expression = term + multiple "+ term"
    term : factor ( '*' factor )* ;  // Term = factor + multiple "* factor"
    factor : INT | '(' expr ')' ;  // Factor = integer or parenthesized expression

    The above rules can correctly parse <span>1 + 2 * 3</span> as <span>1 + (2 * 3)</span>, not as <span>(1 + 2) * 3</span>.

Advanced Features

Antlr also has many advanced features, which will not be studied for now; the basic syntax above is sufficient for this project.

Design of MiniC Lexical Rules

The lexical rules define the basic lexical units in the MiniC language, including keywords, identifiers, literals, operators, and punctuation.

Keywords

MiniC supports the core keywords of the C language, including type specifiers (<span>void</span>, <span>bool</span>, <span>char</span>, <span>int</span>, <span>float</span>), control flow statements (<span>if</span>, <span>else</span>, <span>switch</span>, <span>case</span>, <span>default</span>, <span>while</span>, <span>do</span>, <span>for</span>), jump statements (<span>break</span>, <span>continue</span>, <span>return</span>) etc.

// Keywords
T_VOID: 'void';
T_BOOL: 'bool';
T_CHAR: 'char';
T_INT: 'int';
T_FLOAT: 'float';
T_NULL: 'NULL';
T_TRUE: 'true';
T_FALSE: 'false';
T_IF: 'if';
T_ELSE: 'else';
T_SWITCH: 'switch';
T_CASE: 'case';
T_DEFAULT: 'default';
T_DO: 'do';
T_WHILE: 'while';
T_FOR: 'for';
T_BREAK: 'break';
T_CONTINUE: 'continue';
T_RETURN: 'return';
T_CONST: 'const';

Identifiers

Identifiers are used to represent the names of program entities such as variables, functions, and constants. The MiniC identifier rules are consistent with those of the C language, starting with a letter or underscore, followed by letters, digits, or underscores.

// Identifiers
fragment LETTER: [a-zA-Z];
fragment DIGIT: [0-9];
T_IDENTIFIER: (LETTER | T_UNDERSCORE) (LETTER | DIGIT | T_UNDERSCORE)*;

Literals

MiniC supports four basic literals in the C language: integers, floating-point numbers, characters, and strings.

Integer Literals

MiniC supports four representations of integers: decimal, octal, hexadecimal, and binary:

// Integer Literals
fragment DECIMAL_LITERAL: '0' | [1-9] [0-9]*;
fragment BINARY_LITERAL: '0' [bB] [01]+;
fragment OCTAL_LITERAL: '0' [0-7]+;
fragment HEXADECIMAL_LITERAL: '0' [xX] [0-9a-fA-F]+;
//@warning The decimal integer must be before the octal integer, the order cannot be changed! Otherwise, ambiguity may occur.
T_INTEGER_LITERAL: DECIMAL_LITERAL | BINARY_LITERAL | OCTAL_LITERAL | HEXADECIMAL_LITERAL;

It is important to note that the order of rules is very important. Since octal numbers start with 0, and decimal numbers can also start with 0 (indicating the number 0), the decimal number rule must be placed before the octal number rule to avoid ambiguity.

Floating-Point Numbers

MiniC floating-point numbers support standard C language scientific notation, including various combinations of integer parts, decimal parts, and exponent parts.

The finite automaton (DFA) representation of C language floating-point numbers:

Designing Grammar Rules for a Mini C Language Compiler

Regular expression representation of floating-point numbers:
Regular expression representation of floating-point numbers:
^[+-]?(([0-9]+(\.[0-9]*)?)|(\.[0-9]+))([eE][+-]?[0-9]+)?$

Where:
1. ^[+-]?  
   - Matches an optional sign at the beginning (`+` or `-`), `?` means "0 or 1 time".

2. **(([0-9]+(\.[0-9]*)?)|(\.[0-9]+))**  
   - The core part, matches two forms of numbers:
     - `[0-9]+(\.[0-9]*)?`: Number with integer part.
     - `(\.[0-9]+)`: Number without integer part.

3. **([eE][+-]?[0-9]+)?**  
   - Optional exponent part:
     - `[eE]`: Exponent marker (`e` or `E`);
     - `[+-]?`: Optional exponent sign;
     - `[0-9]+`: Exponent digits;
     - `?` indicates "the entire exponent part is optional".

4. **$**  
   - Matches the end of the string, ensuring no extra characters.

Regular expression converted to Antlr4 rules (Antlr4 rules can be seen as nested regular expressions):

// Floating-point literals
fragment SIGN: [+-];
fragment DECIMAL_FRACTION: (DIGIT_SEQUENCE (T_DOT DIGIT*)) | (T_DOT DIGIT_SEQUENCE);
fragment DECIMAL_EXPONENT: [eE] SIGN? DIGIT_SEQUENCE;
fragment DECIMAL_FLOAT_LITERAL: SIGN? DECIMAL_FRACTION DECIMAL_EXPONENT?;
T_FLOAT_LITERAL: DECIMAL_FLOAT_LITERAL;

Character and String Literals

MiniC supports C language style character and string literals, including escape sequences:

// Character literals
fragment ESCAPE_SEQUENCE: T_BACK_SLASH ([nrtbf] | T_SINGLE_QUOTE | T_DOUBLE_QUOTE | T_BACK_SLASH);
fragment CCHAR: ESCAPE_SEQUENCE | ~['\\];
fragment SCHAR: ESCAPE_SEQUENCE | ~["\\];
T_CHAR_LITERAL: T_SINGLE_QUOTE CCHAR T_SINGLE_QUOTE;
// Strings
T_STRING_LITERAL: T_DOUBLE_QUOTE SCHAR* T_DOUBLE_QUOTE;

Supported escape sequences include newline (<span>\n</span>), carriage return (<span>\r</span>), tab (<span>\t</span>), backspace (<span>\b</span>), form feed (<span>\f</span>), as well as escape for single quote (<span>\'</span>), double quote (<span>\"</span>), and backslash (<span>\\</span>).

Operators and Punctuation

MiniC supports most operators in the C language, including arithmetic operators, bitwise operators, logical operators, relational operators, assignment operators, etc.:

// Arithmetic operators
T_PLUS: '+';
T_MINUS: '-';
T_STAR: '*';
T_SLASH: '/';
T_PERCENT: '%';

// Increment and Decrement operators
T_INCREASE: '++';
T_DECREASE: '--';

// Bitwise operators
T_AMPERSAND: '&amp;';
T_BAR: '|';
T_TILDE: '~';
T_CARET: '^';
T_L_SHIFT: '&lt;&lt;';
T_R_SHIFT: '&gt;&gt;';

// Logical operators
T_AND: '&amp;&amp;';
T_OR: '||';
T_NOT: '!';

// Relational operators
T_LT: '&lt;';
T_GT: '&gt;';
T_LE: '&lt;=';
T_GE: '&gt;=';
T_EQ: '==';
T_NE: '!=';

// Assignment operators
T_ASSIGN: '=';
T_PLUS_ASSIGN: '+= '; 
T_MINUS_ASSIGN: '-= ';
T_STAR_ASSIGN: '*= ';
T_SLASH_ASSIGN: '/= ';
T_PERCENT_ASSIGN: '%= ';
T_AMPERSAND_ASSIGN: '&amp;=';
T_BAR_ASSIGN: '|=';
T_CARET_ASSIGN: '^=';
T_L_SHIFT_ASSIGN: '&lt;&lt;=';
T_R_SHIFT_ASSIGN: '&gt;&gt;=';

Whitespace and Comments

MiniC supports C language style single-line comments (<span>//</span>) and multi-line comments (<span>/* */</span>), which are skipped during lexical analysis (or can be set to automatically generate documentation, similar to Doxygen):

// Comments and Whitespace
T_BLOCK_COMMENT: '/*' .*? '*/' -> skip;  // Multi-line comments
T_LINE_COMMENT: '//' ~[\r\n]* -> skip;   // Single-line comments
T_WHITESPACE: [ \t\r\n]+ -> skip;        // Whitespace (spaces, tabs, newlines)
//! Note: The first item in the matching list of T_WHITESPACE is space, don't forget!

Design of Syntax Rules

The syntax rules define the syntax structure of the MiniC language, describing how lexical units combine into valid program structures. The syntax rules of MiniC are organized according to the hierarchy of program structures, from the top-level compilation unit to the lower-level expressions.

Since modifying the grammar file requires a lot of code changes whenever new features are added, I have defined the grammar all at once, and the comments will be very detailed.

Program Structure

A MiniC program consists of one or more external declarations, which can be function definitions, declaration statements, or empty statements:

// Compilation unit (function declaration | function definition | empty statement)
compilationUnit: translationUnit? EOF;
translationUnit: externalDeclaration+;
externalDeclaration
    : functionDefination      // Function definition
    | declaration             // Declaration statement
    | T_SEMICOLON             // Empty statement
    ;

Function Definitions

A function definition consists of a list of declaration specifiers, a declarator, and a compound statement:

// Function definition (specifier list + declarator + compound statement)
functionDefination: declarationSpecifierList declarator compoundStatement;
/*
declarationSpecifierList corresponds to type specifiers, such as static/const/volatile, etc.
declarator corresponds to function name and parameter list.
compoundStatement corresponds to function body.
*/

Where the declaration specifier list includes type modifiers and type specifiers:

// Declaration specifier list (order does not matter)
declarationSpecifierList: declarationSpecifier+;

// Declaration specifier (type modifier | type)
declarationSpecifier: typeQualifier | typeSpecifier;

// Type modifiers (const | volatile | restrict, etc.)
typeQualifier: T_CONST;

// Type specifiers (currently only supports some basic types)
typeSpecifier: T_VOID | T_BOOL | T_CHAR | T_INT | T_FLOAT;

The declarator part describes the function’s name and parameter list:

// Declarator (pointer + direct declarator)
declarator: pointer? directDeclarator;

// Pointer (supports multiple levels of pointers)
pointer: T_STAR+;

// Direct declaration (variable declaration + function pointer declaration + function declaration)
directDeclarator
    : T_IDENTIFIER                                             // Variable declaration
    | T_L_PAREN declarator T_R_PAREN                           // Function pointer declaration
    | directDeclarator T_L_PAREN parameterList? T_R_PAREN      // Function declaration
    ;

The parameter list consists of one or more parameter declarations:

// Function parameter list (any number of comma-separated parameters)
parameterList: parameterDeclaration (T_COMMA parameterDeclaration)*;

// Function parameter declaration (specifier list + declarator)
parameterDeclaration: declarationSpecifierList declarator;

Compound Statements and Statements

A compound statement consists of a list of block items wrapped in braces, where block items can be statements or declarations:

// Compound statement (code wrapped in braces)
compoundStatement: T_L_BRACE blockItemList? T_R_BRACE;

// Block item list
blockItemList: blockItem+;

// Block item (statement | declaration)
blockItem
    : statement
    | declaration
    ;

MiniC supports various types of statements, including labeled statements, compound statements, expression statements, selection statements, iteration statements, and jump statements:

// Statements (labeled statements | compound statements | expression statements | selection statements | iteration statements | jump statements)
statement
    : labeledStatement       // Labeled statements
    | compoundStatement      // Compound statements
    | expressionStatement    // Expression statements
    | selectionStatement     // Selection statements
    | iterationStatement     // Iteration statements
    | jumpStatement          // Jump statements
    ;

Labeled Statements

Labeled statements are used for <span>switch-case</span> statements and <span>goto</span> statements (these two features may not be added, but are included in the grammar rules for future expansion):

// Labeled statements (custom label | case label | default label)
labeledStatement
    : T_CASE constantExpression T_COLON statement      // case label
    | T_DEFAULT T_COLON statement                      // default label
    ;

Selection Statements

Selection statements include <span>if-else</span> statements and <span>switch</span> statements:

// Selection statements
selectionStatement
    : T_IF T_L_PAREN expression T_R_PAREN statement (T_ELSE statement)?      // if statement
    | T_SWITCH T_L_PAREN expression T_R_PAREN statement                      // switch-case statement
    ;

Iteration Statements

Iteration statements include <span>while</span> loops, <span>do-while</span> loops, and <span>for</span> loops:

// Iteration statements
iterationStatement
    : T_WHILE T_L_PAREN expression T_R_PAREN statement                        // while loop
    | T_DO statement T_WHILE T_L_PAREN expression T_R_PAREN T_SEMICOLON       // do-while loop
    | T_FOR T_L_PAREN forCondition T_R_PAREN statement                        // for loop
    ;

// for loop condition
forCondition: (forDeclaration | expression?) T_SEMICOLON forExpression? T_SEMICOLON forExpression?;
forDeclaration: declarationSpecifierList initDeclaratorList?;
forExpression: assignmentExpression (T_COMMA assignmentExpression)*;

Jump Statements

Jump statements include <span>continue</span>, <span>break</span>, and <span>return</span>:

// Jump statements
jumpStatement: (T_CONTINUE | T_BREAK | T_RETURN expression?) T_SEMICOLON;

Declarations and Initializations

Declaration statements are used to declare variables, supporting initialization:

// Declaration (specifier list + initialized declarator list)
declaration: declarationSpecifierList initDeclaratorList? T_SEMICOLON;

// Initialized declarator list (any number of comma-separated initialized declarators)
initDeclaratorList: initDeclarator (T_COMMA initDeclarator)*;

// Initialized declarator (declarator + assignment operator + initializer)
initDeclarator: declarator (T_ASSIGN initializer)?;

Initializers support assignment expressions and array initializations:

// Initial value (assignment expression | array initialization)
initializer
    : assignmentExpression                              // Assignment expression
    | T_L_BRACE initializerList T_COMMA? T_R_BRACE      // Array initialization
    ;

// Initializer list
initializerList: designation? initializer (T_COMMA designation? initializer)*;

// Designation (for partial initialization, etc.)
designation: designatorList T_ASSIGN;
designatorList: designator+;
designator: T_L_BRACKET constantExpression T_R_BRACKET | T_DOT T_IDENTIFIER;

Expressions

Expressions are the core part of the MiniC language, supporting most expression types in the C language, organized according to operator precedence from low to high:

// Expressions
expression: assignmentExpression (T_COMMA assignmentExpression)*;

// Assignment expressions
assignmentExpression
    : conditionalExpression 
    | unaryExpression assignmentOperator assignmentExpression
    ;

// Conditional expressions
conditionalExpression: logicalOrExpression (T_QUESTION expression T_COLON conditionalExpression)?;

// Logical OR expressions
logicalOrExpression: logicalAndExpression (T_OR logicalAndExpression)*;

// Logical AND expressions
logicalAndExpression: inclusiveOrExpression (T_AND inclusiveOrExpression)*; 

// Bitwise OR expressions
inclusiveOrExpression: exclusiveOrExpression (T_BAR exclusiveOrExpression)*;

// Bitwise XOR expressions
exclusiveOrExpression: andExpression (T_CARET andExpression)*;

// Bitwise AND expressions
andExpression: equalityExpression (T_AMPERSAND equalityExpression)*;

// Equality expressions
equalityExpression: relationalExpression ((T_EQ | T_NE) relationalExpression)*;

// Relational expressions
relationalExpression: shiftExpression ((T_LT | T_GT | T_LE | T_GE) shiftExpression)*;

// Shift expressions
shiftExpression: additiveExpression ((T_L_SHIFT | T_R_SHIFT) additiveExpression)*;

// Additive expressions
additiveExpression: multiplicativeExpression ((T_PLUS | T_MINUS) multiplicativeExpression)*;

// Multiplicative expressions
multiplicativeExpression: unaryExpression ((T_STAR | T_SLASH | T_PERCENT) unaryExpression)*;

// Unary expressions
unaryExpression: unaryOperator? postfixExpression;

// Postfix expressions
postfixExpression
    : primaryExpression (
        T_L_BRACKET expression T_R_BRACKET               // Array subscript
        | T_L_PAREN argumentExpressionList? T_R_PAREN    // Function call
        | postfixOperator                                // Postfix operator
    )*
    ;

// Primary expressions
primaryExpression
    : T_IDENTIFIER                        // L-value
    | T_LITERAL                           // Literal
    | T_L_PAREN expression T_R_PAREN      // Parenthesized expression
    ;

This hierarchical structure ensures the correct evaluation order of expressions, conforming to the operator precedence rules of the C language. For example, for the expression <span>a * b + c * d</span>, according to the rules defined in the grammar, it will first match multiplicativeExpression + multiplicativeExpression, and each multiplicativeExpression will match into unaryExpression * unaryExpression, ultimately building the syntax tree (CST, used for syntax analysis) through multiple recursive matches. When calculating the result, it will compute from the leaf nodes upwards, ultimately returning the overall result.

Grammar Features and Design Considerations

1. Priority and Associativity

The MiniC grammar implicitly defines operator precedence through the hierarchical structure of rules, where outer rules have lower precedence than inner rules. For example, the precedence of assignment expressions is lower than that of conditional expressions, and the precedence of conditional expressions is lower than that of logical OR expressions, and so on. This design ensures the correct evaluation order of expressions.

2. Handling Left Recursion

Antlr4 supports direct left recursion, which greatly simplifies the writing of expression rules. For example, the rule for addition expressions:

expr: expr '+' expr;

This form directly represents “addition expressions are formed by connecting multiplication expressions with plus or minus signs”, which is both concise and intuitive.

References

The project documentation includes the complete grammar file for standard C language provided by Antlr, <span>C.g4</span>, and the MiniC grammar in this project is also simplified based on that file. Interested friends can refer to this file for more details. Interestingly, after writing C language for so many years, you may unlock new syntax that you have never used. The Antlr repository also has more grammar rule templates (C, C++, Java, SQL, JSON, etc.), which you can study if interested, address: Antlr Grammar (https://github.com/antlr/grammars-v4).

Complete Project Address (Under Development)

https://gitee.com/Naezaer/MiniC

Leave a Comment