Class: Rubycc::Front::Parser
- Inherits:
-
Object
- Object
- Rubycc::Front::Parser
- Defined in:
- lib/rubycc/front/parser.rb
Overview
Recursive-descent parser for the C subset. Nonterminals follow the grammar productions of ISO C (6.5.x / 6.7 / 6.8.x):
translation-unit = external-declaration*
external-declaration = type-specifier ";" -- tag only
| type-specifier declarator
( (";" | compound-statement) -- function
(declarator
is a
function)
| ("=" initializer)?
("," declarator ("=" initializer)?)*
";" ) -- variables
declaration-specifiers = (storage-class-specifier | type-specifier)+
storage-class-specifier = "typedef"
type-specifier = "void" | "char" | "short" | "int" | "long"
| "signed" | "unsigned" | "_Bool"
| struct-or-union-specifier | enum-specifier
| typedef-name
typedef-name = identifier
struct-or-union-specifier = struct-or-union identifier?
"{" struct-declaration+ "}"
| struct-or-union identifier
struct-or-union = "struct" | "union"
enum-specifier = "enum" identifier? "{" enumerator-list ","? "}"
| "enum" identifier
enumerator-list = enumerator ("," enumerator)*
enumerator = identifier ("=" constant-expression)?
struct-declaration = type-specifier declarator
("," declarator)* ";"
| struct-or-union-specifier ";" -- anonymous
parameter-type-list = "void"
| parameter-declaration
("," parameter-declaration)*
parameter-declaration = type-specifier declarator
identifier-list = identifier ("," identifier)*
declarator = "*"* direct-declarator
direct-declarator = (identifier | "(" declarator ")")
direct-declarator-suffix*
direct-declarator-suffix = "[" constant-expression? "]"
| "(" parameter-type-list? ")"
| "(" identifier-list ")" -- old style
function-definition = declaration-specifiers declarator
declaration-list? compound-statement
declaration-list = declaration+
abstract-declarator = "*"* direct-abstract-declarator?
direct-abstract-declarator = ("(" abstract-declarator ")")?
direct-declarator-suffix*
compound-statement = "{" block-item* "}"
block-item = declaration | statement
declaration = type-specifier ";"
| type-specifier init-declarator
("," init-declarator)* ";"
init-declarator = declarator ("=" initializer)?
initializer = assignment-expression
| "{" initializer-list ","? "}"
initializer-list = designation? initializer
("," designation? initializer)*
designation = designator+ "="
designator = "[" constant-expression "]" | "." identifier
statement = labeled-statement | return-statement
| expression-statement | selection-statement
| iteration-statement | jump-statement
| compound-statement
labeled-statement = identifier ":" statement
| "case" constant-expression ":" statement
| "default" ":" statement
return-statement = "return" expression? ";"
expression-statement = expression? ";"
selection-statement = "if" "(" expression ")" statement
("else" statement)?
| "switch" "(" expression ")" statement
iteration-statement = "while" "(" expression ")" statement
| "do" statement "while" "(" expression ")" ";"
| "for" "(" for-init expression? ";"
expression? ")" statement
for-init = declaration | expression? ";"
jump-statement = "break" ";" | "continue" ";"
| "goto" identifier ";"
expression = assignment-expression
("," assignment-expression)*
assignment-expression = conditional-expression
(("=" | "+=" | "-=" | "*=" | "/=" | "%="
| "&=" | "|=" | "^=" | "<<=" | ">>=")
assignment-expression)?
conditional-expression = logical-OR-expression
("?" expression ":" conditional-expression)?
constant-expression = conditional-expression
logical-OR-expression = logical-AND-expression
("||" logical-AND-expression)*
logical-AND-expression = inclusive-OR-expression
("&&" inclusive-OR-expression)*
inclusive-OR-expression = exclusive-OR-expression
("|" exclusive-OR-expression)*
exclusive-OR-expression = AND-expression ("^" AND-expression)*
AND-expression = equality-expression ("&" equality-expression)*
equality-expression = relational-expression
(("==" | "!=") relational-expression)*
relational-expression = shift-expression
(("<" | ">" | "<=" | ">=") shift-expression)*
shift-expression = additive-expression
(("<<" | ">>") additive-expression)*
additive-expression = multiplicative-expression
(("+" | "-") multiplicative-expression)*
multiplicative-expression = cast-expression
(("*" | "/" | "%") cast-expression)*
cast-expression = "(" type-name ")" cast-expression
| unary-expression
unary-expression = ("+" | "-" | "!" | "~" | "&" | "*")* cast-expression
| ("++" | "--") unary-expression
| "sizeof" unary-expression
| "sizeof" "(" type-name ")"
type-name = type-specifier abstract-declarator?
postfix-expression = primary-expression
("[" expression "]"
| "(" argument-expression-list? ")"
| "." identifier | "->" identifier
| "++" | "--")*
argument-expression-list = assignment-expression
("," assignment-expression)*
primary-expression = integer-constant | string-literal
| identifier | "(" expression ")"
Binary precedence levels are parsed by a single table-driven left-associative loop (see #parse_left_associative) rather than one hand-written loop per level, so adding an operator or a precedence tier only requires a new table entry. assignment-expression is right-associative and is handled separately (see #parse_assignment_expression), as is conditional-expression (see #parse_conditional_expression), whose third operand recurses back into itself rather than into the tier above.
Defined Under Namespace
Classes: Alignas, Attribute, DeclSpecInfo, EnumTag, IdentifierList, OrdinaryName
Constant Summary collapse
- COMPOUND_ASSIGNMENT_OPERATORS =
Punctuator → AST operator tables, one per precedence tier (weakest binding first).
{ "+=" => :add, "-=" => :sub, "*=" => :mul, "/=" => :div, "%=" => :mod, "&=" => :and, "|=" => :or, "^=" => :xor, "<<=" => :shl, ">>=" => :shr }.freeze
- INCLUSIVE_OR_OPERATORS =
{ "|" => :or }.freeze
- EXCLUSIVE_OR_OPERATORS =
{ "^" => :xor }.freeze
- AND_OPERATORS =
{ "&" => :and }.freeze
- EQUALITY_OPERATORS =
{ "==" => :eq, "!=" => :ne }.freeze
- RELATIONAL_OPERATORS =
{ "<" => :lt, ">" => :gt, "<=" => :le, ">=" => :ge }.freeze
- SHIFT_OPERATORS =
">>" desugars to an arithmetic shift (:shr here names the source operator, which the generator lowers to a signed :sar); a future unsigned type will lower the same :shr to a logical shift instead.
{ "<<" => :shl, ">>" => :shr }.freeze
- ADDITIVE_OPERATORS =
{ "+" => :add, "-" => :sub }.freeze
- MULTIPLICATIVE_OPERATORS =
{ "*" => :mul, "/" => :div, "%" => :mod }.freeze
- DECL_SPECIFIER_KEYWORDS =
The keywords that make up an integer/void type-specifier list (a "struct" specifier is handled on its own). A declaration begins with one or more of these; #normalize_type_specifiers collapses the collected multiset into a single Rubycc::Type. "void" is only ever valid as a function's return type or as the target of a pointer; every other use is rejected by #reject_void_type.
%w[void char short int long signed unsigned _Bool float double __int128].freeze
- BIGGEST_ALIGNMENT =
The x86_64 "biggest alignment" gcc gives a bare
__attribute__((aligned))with no argument (BIGGEST_ALIGNMENT, 16 bytes): the most useful boundary, enough for any scalar or vector type. 16- LAYOUT_ATTRIBUTES =
The GNU attribute names Step 28 gives real layout meaning; every other attribute is accepted and silently discarded. Kept in sync with the preprocessor's __has_attribute answer (see Preprocessor#fold_has_attribute).
%w[aligned packed].freeze
- INIT_ATTRIBUTES =
The GNU attribute names that register a function with the runtime rather than describe it:
constructorputs it in the object's .init_array (the loader calls it before main / at dlopen) anddestructorin .fini_array (at exit / dlclose). Mapped to the array kind the later stages use. Kept in sync with the preprocessor's __has_attribute answer. { "constructor" => :constructor, "destructor" => :destructor }.freeze
- MIN_INIT_PRIORITY =
The priority window these attributes accept, measured by handing
__attribute__((constructor(N)))to gcc and reading back what it emitted: 0..65535 inclusive is taken (0..100 only with a -Wprio-ctor-dtor warning, that range being reserved for the implementation), and anything outside is the hard error "constructor priorities must be integers from 0 to 65535 inclusive". The same measurement showed 65535 is gcc's default:constructor(65535)emits the plain, unnumbered.init_array, exactly as a bareconstructordoes, so an absent priority is represented as 65535 here and the two spellings coincide downstream just as they do in gcc. ObjFile::ELFWriter::DEFAULT_ARRAY_PRIORITY is the same number on the other side of the IR, where it decides the section's name. 0- MAX_INIT_PRIORITY =
65535- DEFAULT_INIT_PRIORITY =
65535- RESTRICT_SPELLINGS =
The spellings of the "restrict" type qualifier this subset recognizes. ISO "restrict" is not a keyword here (it never gains semantics — a restricted pointer is treated like any other), and glibc prototypes use the reserved GNU spellings "__restrict"/"restrict" unconditionally, so all three arrive as ordinary identifiers and are accepted and discarded wherever a pointer or array-parameter qualifier may appear.
%w[restrict __restrict __restrict__].freeze
- ATOMIC_BUILTINS =
The gcc _atomic* builtins this subset lowers, mapping each keyword to its [AST::BuiltinAtomic kind, argument count]. The nine object forms cover <ruby/atomic.h>; the fence is also supported because C11 library headers and libev use it without an _Atomic object. The test-and-set and the generic (non-"_n") address-taking forms remain deliberately absent, so a program using one of those gets an "undeclared identifier" rather than a silently wrong lowering. (The legacy _sync* family has its own table below.)
The counts include the trailing memory-order argument(s) gcc's signatures take — one for every form but __atomic_compare_exchange_n, which takes a
weakflag and two orders (success and failure). { "__atomic_load_n" => [:load, 2], "__atomic_store_n" => [:store, 3], "__atomic_exchange_n" => [:exchange, 3], "__atomic_compare_exchange_n" => [:compare_exchange, 6], "__atomic_fetch_add" => [:fetch_add, 3], "__atomic_fetch_sub" => [:fetch_sub, 3], "__atomic_add_fetch" => [:add_fetch, 3], "__atomic_sub_fetch" => [:sub_fetch, 3], "__atomic_or_fetch" => [:or_fetch, 3], "__atomic_thread_fence" => [:fence, 1] }.freeze
- SYNC_BUILTINS =
The legacy gcc _sync* builtins this subset lowers, mapping each keyword to its [AST::BuiltinSync kind, argument count]. These predate the _atomic* family and differ from it in two ways that matter here: each one is a full barrier by definition, so none takes a memory-order argument, and the two compare-and-swap forms take the value they expect directly rather than through a pointer.
The set is exactly the forms an existing IR op already gives the right meaning for. The bitwise members with no matching op — __sync_fetch_and_or, __sync_fetch_and_and, __sync_fetch_and_xor, __sync_fetch_and_nand, __sync_and_and_fetch, __sync_xor_and_fetch and __sync_nand_and_fetch — stay deliberately absent for the same reason the missing _atomic* forms do: a program using one gets an "undeclared identifier" instead of a silently wrong lowering.
gcc tolerates extra trailing arguments on all of these (its documented but ignored list of variables to protect). rubycc requires the exact count, so a miscount is reported here rather than quietly dropped.
{ "__sync_fetch_and_add" => [:fetch_add, 2], "__sync_fetch_and_sub" => [:fetch_sub, 2], "__sync_add_and_fetch" => [:add_fetch, 2], "__sync_sub_and_fetch" => [:sub_fetch, 2], "__sync_or_and_fetch" => [:or_fetch, 2], "__sync_lock_test_and_set" => [:exchange, 2], "__sync_lock_release" => [:release, 1], "__sync_synchronize" => [:fence, 0], "__sync_bool_compare_and_swap" => [:bool_compare_and_swap, 3], "__sync_val_compare_and_swap" => [:val_compare_and_swap, 3] }.freeze
- OVERFLOW_BUILTINS =
The gcc overflow-checked arithmetic builtins, mapping each keyword to its AST::BuiltinOverflow operator. All three take the same three arguments (the two operands and the pointer the result is stored through), so the operator is the only thing the spelling decides. The width-suffixed forms (__builtin_uaddll_overflow and kin) are deliberately absent: the generic forms cover every use here, and a missing one is an "undeclared identifier" rather than a wrong lowering.
{ "__builtin_add_overflow" => :add, "__builtin_sub_overflow" => :sub, "__builtin_mul_overflow" => :mul }.freeze
- MAX_NESTING_DEPTH =
The hard ceiling on how deeply the recursive descent will nest before it rejects an input rather than recurse further. A hostile source (tens of thousands of nested parentheses, unary operators, braces, ...) would otherwise drive the descent until the Ruby machine stack overflows, raising a bare SystemStackError that escapes as an unhandled crash instead of a diagnostic. Capping the depth turns that into an ordinary located CompileError.
The value is deliberately well below the depth at which the stack actually gives out. On this toolchain the full pipeline (parser plus IR generation plus the backend, all of which recurse over the same AST) overflows at roughly 330 nested parentheses — the parenthesized- expression path is the most expensive, spending the entire binary- precedence chain per level. A single counter is shared across every recursive path — parenthesized/unary/cast/ternary/assignment expressions, compound statements, initializer lists, nested declarators and struct/union bodies — because these forms interleave (an expression inside a statement inside an initializer ...), so it is their combined live depth that threatens the stack, and bounding it here also bounds the AST depth every later pass recurses over.
Because the expression grammar's right-recursive tiers each carry their own guard (assignment, conditional, unary, cast), one parenthesized level descends through several of them, so the counter climbs about 4 per nested parenthesis — the worst multiplier of any construct. 500 therefore admits roughly 122 nested parentheses: comfortably above C11 §5.2.4.1's 63-level implementation minimum, and about 12x the deepest nesting real inputs reach (measured: 41 in the c-testsuite, 32 for the ruby.h smoke header graph, 22 in the examples). At that ceiling the parser rejects after ~4900 live frames, well under the ~13000 at which Ruby's stack gives out, leaving headroom for a caller that starts from a deeper stack.
500- STORAGE_CLASS_KEYWORDS =
The storage-class specifiers (6.7.1): at most one may appear in a declaration. "typedef", "static" and "extern" are recorded in DeclSpecInfo#storage and consumed downstream, while "register" and "auto" are accepted for compatibility but carry no effect in this subset, so they are consumed without being recorded; all five still participate in the "at most one storage class" duplicate check.
%w[typedef static extern register auto].freeze
Instance Method Summary collapse
-
#initialize(tokens, plain_char: Type::Char, unnamed_bitfields_align: false, builtin_va_list: Type::BuiltinVaList) ⇒ Parser
constructor
plain_charis the Rubycc::Type a barechartype-specifier resolves to. -
#parse ⇒ Object
Parses the whole translation unit into an AST::Program.
Constructor Details
#initialize(tokens, plain_char: Type::Char, unnamed_bitfields_align: false, builtin_va_list: Type::BuiltinVaList) ⇒ Parser
plain_char is the Rubycc::Type a bare char type-specifier resolves
to. Its signedness is implementation-defined and pinned per ABI, so the
caller that knows the target hands it in (see Compiler#compile);
defaulting to the signed instance keeps a target-less caller on the
x86-64 System V choice. signed char and unsigned char are unaffected —
both are separate types with a fixed signedness.
unnamed_bitfields_align is the second such per-ABI trait: whether an
unnamed bit-field's type raises its aggregate's alignment (it does under
AAPCS64, not under the x86-64 System V psABI). It is passed straight to
StructType#define, which documents the rule.
builtin_va_list is the third: the type __builtin_va_list names, whose
tag layout differs between the ABIs (four fields on System V, five on
AAPCS64). The caller hands in the target's from its CallConvention so the
typedef the parser seeds below reserves the right-sized object and, being
the same tag instance the generator type-checks against, is recognized by
identity there.
398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 |
# File 'lib/rubycc/front/parser.rb', line 398 def initialize(tokens, plain_char: Type::Char, unnamed_bitfields_align: false, builtin_va_list: Type::BuiltinVaList) @tokens = tokens @plain_char = plain_char @unnamed_bitfields_align = unnamed_bitfields_align @builtin_va_list = builtin_va_list @pos = 0 # The number of recursive-descent nesting levels currently live, capped # at MAX_NESTING_DEPTH by #with_nesting_guard. One counter is shared by # every recursive construct so their interleaved depth is what is bounded. @nesting_depth = 0 # Struct and enum tags live in their own namespace, separate from # variables and functions, and follow the same block scoping. # @tag_scopes is a stack of "tag name -> Type::StructType | EnumTag" # maps, innermost last, with the file scope at the bottom; a # compound-statement (and a for-loop's own parentheses, and a function # body) pushes a fresh map so a tag defined inside a block shadows an # outer one and vanishes at the block's end. Tag resolution happens here, # at parse time, because every other type is built here too — the # generator only ever consumes finished Type objects. @tag_scopes = [{}] # The ordinary-identifier namespace, scoped in lockstep with @tag_scopes: # a stack of "name -> OrdinaryName" maps. It records typedef names # (resolved to a Type), enum constants (resolved to an Integer) and the # plain declarator names that shadow them, so a name is looked up here to # decide whether an identifier opens a declaration (a typedef name), folds # to a constant (an enumerator) or is an ordinary reference. The outermost # scope is pre-seeded with `__builtin_va_list` as a typedef for the # target's va_list type (a one-element __va_list_tag array), exactly as # gcc predeclares it, so "__builtin_va_list ap;" is parsed as a # declaration with no dedicated keyword and a program may still shadow the # name. @ordinary_scopes = [{ "__builtin_va_list" => OrdinaryName.new(:typedef, [@builtin_va_list, false]) }] # The constructor/destructor registrations the unit asked for, keyed by # function name (see #register_init_attributes). Filled as declarations # are read and handed to AST::Program whole, because the attribute may be # written on a prototype that precedes *or* follows the definition, so no # single declaration node can be the one that carries it. @init_attributes = {} # GNU visibility attributes are also declaration-order independent: # Ruby's exported-function macro puts the explicit default visibility # on a prototype, while the definition appears later without it. @visibility_attributes = {} # The parameter types each file-scope function *prototype* declared, # keyed by name. Only one construct reads them: an old-style definition # of a name a prototype already declared, which 6.7.6.3p14 checks # against that prototype and which is then passed its arguments in the # prototype's form rather than the promoted one (see # #old_style_parameter_abi_types). Every other agreement between # declarations of one function is the generator's to enforce. @prototype_param_types = {} end |
Instance Method Details
#parse ⇒ Object
Parses the whole translation unit into an AST::Program. An external declaration yields a single node (a function) or, for a comma-separated run of global variables, an array of GlobalDecl; both are flattened into one source-ordered list.
455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 |
# File 'lib/rubycc/front/parser.rb', line 455 def parse declarations = [] until peek.eof? # GCC accepts a stray semicolon at file scope as an empty external # declaration. X-macro headers commonly leave one after a macro that # already emits semicolon-terminated declarations (for example pg's # GVL wrapper table), so consume the GNU extension here. if peek.punct?(";") advance next end node = parse_external_declaration node.is_a?(Array) ? declarations.concat(node) : declarations << node end AST::Program.new(declarations, @init_attributes, @visibility_attributes) end |