DGCC language subset grammar

An EBNF-ish reference for the C subset nparse.c accepts, after cpp.c has already resolved #define/#include/conditionals. { } means zero or more, [ ] means optional, | means alternation, literals are quoted. See DESIGN.md for the full list of deliberately-unsupported constructs (struct, the comma operator, multi-dimensional arrays, and so on) and other simplifications.

Lexical

identifier   = letter { letter | digit | "_" } ;
letter       = "a".."z" | "A".."Z" | "_" ;
number       = digit { digit } ;
char-literal = "'" ( any-char | escape ) "'" ;
string-lit   = '"' { any-char | escape } '"' ;
escape       = "\" ( "n" | "t" | "0" | "\" | "'" | '"' ) ;
comment      = "/*" ... "*/" ;   (* only block comments *)

Program structure

translation-unit = { top-level-decl } ;

top-level-decl = typedef-decl
                | function-decl
                | function-def
                | global-var-decl ;

typedef-decl = "typedef" type-spec declarator ";" ;

type-spec = ( "int" | "char" | "void" | typedef-name ) ;

declarator = { "*" } identifier ;

function-decl = [ "extern" ] type-spec declarator
                "(" param-list ")" ";" ;

function-def  = [ "static" ] type-spec declarator
                "(" param-list ")" compound-stmt ;

param-list = "void"
           | [ param { "," param } ] ;
param      = type-spec declarator [ "[" "]" ] ;

global-var-decl = [ "static" | "extern" ] type-spec
                   init-declarator { "," init-declarator } ";" ;
init-declarator = declarator [ "[" [ const-expr ] "]" ]
                   [ "=" initializer ] ;
initializer = expr
            | string-lit
            | "{" expr { "," expr } "}" ;
const-expr = [ "-" ] const-term { ( "+" | "-" ) const-term } ;
const-term = const-factor { ( "*" | "/" ) const-factor } ;
const-factor = number | char-literal | "(" const-expr ")" ;
             (* array sizes, local or global, may be any such constant
                expression, not just a bare literal -- e.g. "[N + 1]" *)

Statements

compound-stmt = "{" { local-decl } { statement } "}" ;

local-decl = type-spec init-declarator-list ";" ;
             (* a declaration may start any compound-stmt, not just a
                function's outer one -- but it is hoisted into that
                function's one flat frame, not a real nested scope, so
                the same name can't be reused across sibling blocks the
                way real C scoping would allow (see DESIGN.md's
                "Interim block scoping"); local array initializers are
                a caught error, not silently accepted *)

statement = compound-stmt
          | if-stmt
          | while-stmt
          | do-while-stmt
          | for-stmt
          | switch-stmt
          | asm-line
          | "break" ";"
          | "continue" ";"
          | "return" [ expr ] ";"
          | [ expr ] ";" ;

if-stmt       = "if" "(" expr ")" statement [ "else" statement ] ;
while-stmt    = "while" "(" expr ")" statement ;
do-while-stmt = "do" statement "while" "(" expr ")" ";" ;
for-stmt      = "for" "(" [ expr ] ";" [ expr ] ";" [ expr ] ")" statement ;

switch-stmt   = "switch" "(" expr ")" "{" { local-decl }
                { case-label | statement } "}" ;
case-label    = ( "case" const-expr | "default" ) ":" ;
                (* case/default are recognized only at this top level of
                   a switch's own body, not inside a further-nested
                   block within it -- no Duff's-device-style buried case
                   labels. Real fall-through: nothing is implied between
                   one case's statements and the next unless a "break"
                   says otherwise. Inside a switch, "continue" skips
                   past it to search for the nearest enclosing *loop* --
                   a switch provides a "break" target but not a
                   "continue" one, same as real C. *)

asm-line      = ( "#asm" | "#a" ) <rest of source line, verbatim> ;
                (* a preprocessor directive (handled by cpp.c, not a
                   grammar production nparse.c itself recognizes as
                   such), listed here because it's valid wherever a
                   statement is, as well as at file scope outside any
                   function -- see docs/DESIGN.md's "Inline assembly".
                   No trailing ";": the directive's own line already
                   ends it. *)

Expressions

Precedence from loosest to tightest binding (top of the list binds loosest), all left-associative except assignment and the unary/cast level:

expr            = assignment ;

assignment      = conditional [ assign-op assignment ] ;
assign-op       = "=" | "+=" | "-=" | "*=" | "/=" | "%="
                | "&=" | "|=" | "^=" | "<<=" | ">>=" ;

conditional     = logical-or [ "?" assignment ":" conditional ] ;

logical-or      = logical-and { "||" logical-and } ;
logical-and     = bit-or { "&&" bit-or } ;
bit-or          = bit-xor { "|" bit-xor } ;
bit-xor         = bit-and { "^" bit-and } ;
bit-and         = equality { "&" equality } ;
equality        = relational { ( "==" | "!=" ) relational } ;
relational      = shift { ( "<" | "<=" | ">" | ">=" ) shift } ;
shift           = additive { ( "<<" | ">>" ) additive } ;
additive        = multiplicative { ( "+" | "-" ) multiplicative } ;
multiplicative  = unary { ( "*" | "/" | "%" ) unary } ;

unary           = ( "+" | "-" | "!" | "~" | "*" | "&" ) unary
                | "++" unary
                | "--" unary
                | "(" type-spec { "*" } ")" unary        (* cast *)
                | "sizeof" "(" type-spec { "*" } ")"
                | postfix ;

postfix         = primary { "[" expr "]"
                           | "(" [ arg-list ] ")"
                           | "++"
                           | "--" } ;
arg-list        = expr { "," expr } ;

primary         = identifier
                | number
                | char-literal
                | string-lit
                | "(" expr ")" ;

Notes on the expression grammar that matter for what actually compiles:

  • && and || short-circuit (compiled as real branches, not bitwise ops).
  • conditional (?:) is right-associative, so a ? b : c ? d : e parses as a ? b : (c ? d : e). Its result type is simply the true-branch's -- there is no common-type unification between the two arms, a documented simplification (see DESIGN.md).
  • Pointer arithmetic in additive is type-aware: ptr + int and ptr - int preserve the pointer type (see DESIGN.md's byte-pointer section for what "preserve" means for char * specifically); int arrays and pointers never need scaling since they're already one-word-per-element.
  • assignment's left-hand side must be a bare lvalue expression (identifier, *expr, arr[i], or a struct-free member chain thereof built from those) -- (x) = 5 specifically does not work, a known narrow gap (see DESIGN.md).
  • sizeof only accepts a parenthesized type name, never an expression (sizeof(x) is not the same feature as sizeof(int) here -- only the type-name form is implemented).