Skip to content

Latest commit

 

History

History
executable file
·
1924 lines (1773 loc) · 58.3 KB

README.markdown

File metadata and controls

executable file
·
1924 lines (1773 loc) · 58.3 KB
Raw

CAST

C parser and abstract syntax tree for Ruby.

Example

require 'cast'

source = File.read('file.c')
ast = C.parse(source)
ast.entities.each do |declaration|
  declaration.declarator.each do |declarator|
    puts "#{declarator.name}: declarator.type"
  end
end

Or in irb:

irb> ast = C.parse('int main(void) { return 0; }')
 => TranslationUnit
    entities:
        - FunctionDef
            type: Function
                type: Int
                params: []
            name: "main"
            def: Block
                stmts:
                    - Return
                        expr: IntLiteral
                            val: 0

irb> puts ast
int main(void) {
    return 0;
}
 => nil

Nodes

C.parse returns a tree of Node objects. Here's the class hierarchy:

  • Node
    • TranslationUnit
    • Comment
    • Declaration
    • Declarator
    • FunctionDef
    • Parameter
    • Enumerator
    • MemberInit
    • Member
    • Statement
      • Block
      • If
      • Switch
      • While
      • For
      • Goto
      • Continue
      • Break
      • Return
      • ExpressionStatement
    • Label
      • PlainLabel
      • Default
      • Case
    • Type
      • IndirectType
        • Pointer
        • Array
        • Function
      • DirectType
        • Struct
        • Union
        • Enum
        • CustomType
        • PrimitiveType
          • Void
          • Int
          • Float
          • Char
          • Bool
          • Complex
          • Imaginary
    • Expression
      • Comma
      • Conditional
      • Variable
      • UnaryExpression
        • PostfixExpression
          • Index
          • Call
          • Dot
          • Arrow
          • PostInc
          • PostDec
        • PrefixExpression
          • Cast
          • Address
          • Dereference
          • Sizeof
          • Plus
          • Minus
          • PreInc
          • PreDec
          • BitNot
          • Not
      • BinaryExpression
        • Add
        • Subtract
        • Multiply
        • Divide
        • Mod
        • Equal
        • NotEqual
        • Less
        • More
        • LessOrEqual
        • MoreOrEqual
        • BitAnd
        • BitOr
        • BitXor
        • ShiftLeft
        • ShiftRight
        • And
        • Or
      • AssignmentExpression
        • Assign
        • MultiplyAssign
        • DivideAssign
        • ModAssign
        • AddAssign
        • SubtractAssign
        • ShiftLeftAssign
        • ShiftRightAssign
        • BitAndAssign
        • BitXorAssign
        • BitOrAssign
      • Literal
        • StringLiteral
        • CharLiteral
        • CompoundLiteral
        • IntLiteral
        • FloatLiteral
    • NodeList
      • NodeArray
      • NodeChain

The bold ones are abstract.

The last 2 (NodeLists) represent lists of Nodes. They quack like standard ruby Arrays. NodeChain is a doubly linked list; NodeArray is an array.

Node Methods

  • parent: return the parent in the tree (a Node or nil).

  • pos, pos=: the position in the source file (a Node::Pos).

  • to_s: return the code for the tree (a String).

  • inspect: return a pretty string for inspection, makes irb fun.

  • match?(str), =~(str): return true iff str parses as a Node equal to this one.

  • detach: remove this node from the tree (parent becomes nil) and return it.

  • detached?, attached?: return true if parent is nil or non-nil respectively.

  • replace_with(node): replace this node with node in the tree.

  • swap_with(node): exchange this node with node in their trees.

  • insert_prev(*nodes), insert_next(*nodes): insert nodes before this node in the parent list. Parent must be a NodeList! Useful for adding statements before a node in a block, for example.

  • Foo?: (where Foo is a module name) return self.is_a?(Foo). This is a convienience for a common need. Example:

    \# print all global variables
ast.entities.each do |node|
  node.Declaration? or next
  node.declarators.each do |decl|
    unless decl.type.Function?
      puts "#{decl.name}: #{decl.type}"
    end
  end
end

The =~ method lets you do:

if declarator.type =~ 'const int *'
  puts "Ooh, a const int pointer!"
end

This is not the same as declarator.type.to_s == 'const int *'; that'd require you to guess how to_s formats its strings (most notably, the whitespace).

Fields and Children

The big table down below lists the fields of each Node. A field is an attribute which:

  • is used in equality checks (== and eql?).
  • are copied recursively by dup and clone.

Fields listed as children form the tree structure. They only have a Node or nil value, and are yielded/returned/affected by the traversal methods:

  • next, prev: return the next/prev sibling.
  • list_next, list_prev: like next/prev, but also requires the parent to be NodeList. I'll be honest; I don't remember why I added these methods. They may well suddenly disappear.
  • each, reverse_each: Yield all (non-nil) children. Node includes Enumerable, so, you know.
  • depth_first, reverse_depth_first: Walk the tree in that order, yielding two args (event, node) at each node. event is :down on the way down, :up on the way up. If the block throws :prune, it won't descend any further.
  • preorder, reverse_preorder, postorder, reverse_postorder: Walk the tree depth first, yielding nodes in the given order. For the preorders, if the block throws :prune, it won't descend any further.
  • node_after(child), node_before(child): return the node before/after child (same as child.next).
  • remove_node(child): remove child from this node (same as child.detach).
  • replace_node(child, new_child): replace child with yeah you guessed it (same as child.replace_with(newchild)).

Note: don't modify the tree during traversal!

Other notes about the table:

  • Field names that end in '?' are always true-or-false.
  • If no default is listed:
    • it is false if the field name ends in a '?'
    • it is a NodeArray if it is a NodeList.
    • it is nil otherwise.
<style> table.node_desc tr.first_field td { border-top: 1px solid black; } 
table.node_desc tr.first_field table td {
  border: none;
}

table.node_desc td {
  padding: 3px;
  vertical-align: top;
{

table.node_desc table td {
  padding: 0px;
{
</style>
Class Field Type / values Default Comments
TranslationUnit entities * NodeList NodeChain[] The root of a parsed file.
Declaration storage :typedef, :extern, :static, :auto, :register Also:
  • #typedef? -- true iff storage == :typedef
  • #extern? -- true iff storage == :extern
  • #static? -- true iff storage == :static
  • #auto? -- true iff storage == :auto
  • #register? -- true iff storage == :register
type * DirectType
declarators * NodeList NodeArray[]
inline? true, false
Declarator indirect_type * IndirectType What's a "declarator?" Consider "int i, *ip;". This is a Declaration with two Declarators: 
    Declaration
        type: Int
        declarators:
            - Declarator
                name: "i"
            - Declarator
                indirect_type: Pointer
                name: "ip"
The indirect_type of the ip Declarator is a Pointer to nil. To get the complete type of the variable use:
  • #type -- return the complete type. This is a clone; modifying it won't modify the tree.
So calling #type on the ip Declarator gives: 
    Pointer
      type: Int
name String
init * Expression
num_bits * Integer
FunctionDef storage :extern, :static Also:
  • #extern? -- return true iff storage == :extern
  • #static? -- return true iff storage == :static
  • #prototype? -- same as !no_prototype?
  • #prototype=(val) -- same as no_prototype = !val
no_prototype? means that no prototype was given. That means parameter types weren't given in the parens, but in the "old-style" declaration list. Example: 
int main(argc, argv)
    int argc;
    char **argv;
{
    return 0;
}
 
int main(int argc, char **argv) {
    return 0;
}
No prototype Prototype
Everyone tells you to use prototypes. That's because no type checking is done when calling a function declared without a prototype.
inline? true, false
type * Type
name String
def * Block Block.new
no_prototype? true, false
Parameter register? true, false Used in Functions.
type * Type
name String
Enumerator name String Used in Enums.
val * Expression
MemberInit member * NodeList of (Member or Expression) Used in CompoundLiterals.
init * Expression
Member name String Used in MemberInits.
Block labels * NodeList of Label NodeArray[]
stmts * NodeList of (Statement or Declaration or Comment) NodeArray[]
If labels * NodeList of Label NodeArray[]
cond * Expression
then * Statement
else * Statement
Switch labels * NodeList of Label NodeArray[]
cond * Expression
stmt * Statement
While labels * NodeList of Label NodeArray[] do? means it's a do-while loop.
do? true, false
cond * Expression
stmt * Statement
For labels * NodeList of Label NodeArray[]
init * Expression or Declaration
cond * Expression
iter * Expression
stmt * Statement
Goto labels * NodeList of Label NodeArray[]
target String
Continue labels * NodeList of Label NodeArray[]
Break labels * NodeList of Label NodeArray[]
Return labels * NodeList of Label NodeArray[]
expr * Expression
ExpressionStatement labels * NodeList of Label NodeArray[]
expr * Expression
PlainLabel name String
Default
Case expr * Expression
Comma exprs * NodeList of Expression
Conditional cond * Expression
then * Expression
else * Expression
Variable name String
Index expr * Expression
index * Expression
Call expr * Expression
args * NodeList of (Expression or Type)
Dot expr * Expression
member * String
Arrow expr * Expression
member * String
PostInc expr * Expression
PostDec expr * Expression
Cast type * Type
expr * Expression
Address expr * Expression
Dereference expr * Expression
Sizeof expr * Type or Expression
Positive expr * Expression
Negative expr * Expression
PreInc expr * Expression
PreDec expr * Expression
BitNot expr * Expression
Not expr * Expression
Add expr1 * Expression
expr2 * Expression
Subtract expr1 * Expression
expr2 * Expression
Multiply expr1 * Expression
expr2 * Expression
Divide expr1 * Expression
expr2 * Expression
Mod expr1 * Expression
expr2 * Expression
Equal expr1 * Expression
expr2 * Expression
NotEqual expr1 * Expression
expr2 * Expression
Less expr1 * Expression
expr2 * Expression
More expr1 * Expression
expr2 * Expression
LessOrEqual expr1 * Expression
expr2 * Expression
MoreOrEqual expr1 * Expression
expr2 * Expression
BitAnd expr1 * Expression
expr2 * Expression
BitOr expr1 * Expression
expr2 * Expression
BitXor expr1 * Expression
expr2 * Expression
ShiftLeft expr1 * Expression
expr2 * Expression
ShiftRight expr1 * Expression
expr2 * Expression
And expr1 * Expression
expr2 * Expression
Or expr1 * Expression
expr2 * Expression
Assign lval * Expression
rval * Expression
MultiplyAssign lval * Expression
rval * Expression
DivideAssign lval * Expression
rval * Expression
ModAssign lval * Expression
rval * Expression
AddAssign lval * Expression
rval * Expression
SubtractAssign lval * Expression
rval * Expression
ShiftLeftAssign lval * Expression
rval * Expression
ShiftRightAssign lval * Expression
rval * Expression
BitAndAssign lval * Expression
rval * Expression
BitXorAssign lval * Expression
rval * Expression
BitOrAssign lval * Expression
rval * Expression
StringLiteral val String The String in val is the literal string entered. "\n" isn't converted to a newline, for instance.
CharLiteral val String The String in val is the literal string entered. '\n' isn't converted to a newline, for instance.
CompoundLiteral type * Type

Here's an example:

(struct S){1, .x = 2, .y [3] .z = 4}

parses as:

CompoundLiteral
    type: Struct
        name: "S"
    member_inits:
        - MemberInit
            init: IntLiteral
                val: 1
        - MemberInit
            member:
                - Member
                    name: "x"
            init: IntLiteral
                val: 2
        - MemberInit
            member:
                - Member
                    name: "y"
                - IntLiteral
                    val: 3
                - Member
                    name: "z"
            init: IntLiteral
                val: 4
member_inits * NodeList of MemberInit NodeArray[]
IntLiteral format :dec, :hex, :oct :dec

Also:

  • #dec? -- return true iff format == :dec
  • #hex? -- return true iff format == :hex
  • #oct? -- return true iff format == :oct
val Integer
suffix String
FloatLiteral format :dec, :hex :dec
val Float
exponent Integer
suffix String
Pointer const? true, false
restrict? true, false
volatile? true, false
type * Type
Array const? true, false
restrict? true, false
volatile? true, false
type * Type
length * Expression
Function const? true, false
restrict? true, false
volatile? true, false
type * Type
params * NodeList of Parameter NodeArray[]
var_args? true, false
Struct const? true, false
restrict? true, false
volatile? true, false
name String
members * NodeList of Member NodeArray[]
Union const? true, false
restrict? true, false
volatile? true, false
name String
members * NodeList of Member NodeArray[]
Enum const? true, false
restrict? true, false
volatile? true, false
name String
members * NodeList of Enumerator
CustomType const? true, false For typedef'd names.
restrict? true, false
volatile? true, false
name String
Void const? true, false const is for things like const void *.
restrict? true, false
volatile? true, false
Int const? true, false Also:
  • #short? -- return true iff longness == -1
  • #plain? -- return true iff longness == 0
  • #long? -- return true iff longness == 1
  • #long_long? -- return true iff longness == 2
  • #signed? -- same as !unsigned?
  • #signed=(val) -- same as unsigned = !val
restrict? true, false
volatile? true, false
longness -1, 0, 1, 2 0
unsigned? true, false
Float const? true, false Also:
  • #plain? -- return true iff longness == 0
  • #double? -- return true iff longness == 1
  • #long_double? -- return true iff longness == 2
restrict? true, false
volatile? true, false
longness 0, 1, 2 0
Char const? true, false Also:
  • #signed? -- return true iff signed == true
  • #unsigned? -- return true iff signed == false
  • #plain? -- return true iff signed == nil
Yes, C99 says that char, signed char, and unsigned char are 3 distinct types (unlike with int -- go figure). Like Martian chalk and Venusian cheese: completely different, but you can fit 'em each in one byte.
restrict? true, false
volatile? true, false
signed true, false, nil
Bool const? true, false This is the rarely seen _Bool type.
restrict? true, false
volatile? true, false
Complex const? true, false

This is the rarely seen _Complex type.

  • #plain? -- return true iff longness == 0
  • #double? -- return true iff longness == 1
  • #long_double? -- return true iff longness == 2
restrict? true, false
volatile? true, false
longness 0, 1, 2 0
Imaginary const? true, false

This is the rarely seen _Imaginary type.

  • #plain? -- return true iff longness == 0
  • #double? -- return true iff longness == 1
  • #long_double? -- return true iff longness == 2
restrict? true, false
volatile? true, false
longness 0, 1, 2 0
BlockExpression block * Block Block.new Only if the block_expressions extension is enabled. See "Extensions" section below.

Parser

C.parse will use the default parser (C.default_parser), but you can also manage your own parser(s) if you need finer control over state. Parser state consists of:

  • type_names: a Set of Strings. As a parser eats typedefs, this grows.
  • pos: the Node::Pos this parser will start parsing at.

A Node::Pos has three read-write attributes: filename, line_num, col_num. Default is nil, 1, 0.

Note that the type names the parser has seen affects the parser! For example, consider:

a * b;
  • If only a is a type, this is a declaration.
  • If neither a nor b are types, this is a multiplication statement.
  • Otherwise, it's a syntax error.

You may append type names implicitly, by parsing typedefs, or explicitly like this:

parser.type_names << 'Thing' << 'OtherThing'

Parsing Snippets

C.parse will parse the toplevel C construct, a C::TranslationUnit, but you can also parse other snippets of C:

C::Statement.parse('while (not_looking) { paint_car(); }')
C::Type.parse('void *(*)(int *(*)[][2], ...)')

This works for both concrete and abstract Node subclasses. A Parser may be given as an optional second argument.

Extensions to C99

  • Types are allowed as function arguments. This is needed to parse C99 macros like va_arg().
  • Blocks in parentheses are allowed as expressions (a gcc extension). You need to call parser.enable_block_expressions first. They appear as BlockExpression nodes.

Parsing Full Programs

This can be tricky for a number of reasons. Here are the issues you'll likely encounter.

Preprocessing

Directives that start with # are not handled by the Parser, as they're external to the C grammar. CAST ships with a Preprocessor, which wraps the preprocessor used to build your Ruby interpreter.

cpp = C::Preprocessor.new
cpp.include_path << '/usr/include' << /usr/local/include'
cpp.macros['DEBUG'] = '1'
cpp.macros['max(a, b)'] = '((a) > (b) ? (a) : (b))'
cpp.preprocess(code)

Note however, that preprocessors tend to leave vendor-specific extensions in their output. GNU cpp, for example, leaves "linemarkers" (lines that begin with #) in the output which you'll need to filter out manually before feeding it to a Parser.

Built-in types

Mac OS 10.5's system cpp for instance assumes the compiler will recognize types such as __darwin_va_list.

Syntactic Extensions

Some code may take advantage of compiler-specific extensions to the syntax. For example, gcc supports inline assembly via directives like:

asm("movl %1, %%eax;
    "movl %%eax, %0;"
    :"=r"(y)
    :"r"(x)
    :"%eax");

Such code is fairly rare, so there is no direct support in CAST for this. You'll need to manually massage such constructs out of the Parser input. Or send me patches. Delicious patches.

Contributing

  • Bug reports
  • Source
  • Patches: Fork on Github, send pull request.
    • Include tests where practical.
    • Leave the version alone, or bump it in a separate commit.

Copyright

Copyright (c) George Ogata. See LICENSE for details.