4 ms·

How is it usually done in most high performance compilers, if I may ask?

by farresito 10y ago

nv-vn 10y ago
Parsed by hand
- posterboy 10y ago
  That strikes me as odd, but who am I to argue with the wisdom of the crowd. http://stackoverflow.com/questions/6319086/are-gcc-and-clang-parsers-really-handwritten http://stackoverflow.com/questions/6319086/are-gcc-and-clang... (short answer, yes)
lallysingh 10y ago
C++ is a context sensitive language, so (at least some) hand parsing is necessary.
- munificent 10y ago
  You can use a generated parser for C/C++, I believe. You just need to insert a little shim between the lexer and parser to look up identifiers in the symbol table and mark which name tokens refer to types versus functions or variables.
  - joshuata 10y ago
    You are (essentially) correct. The language itself is context-free, and therefore parse-able as a regular language. Looking up identifiers in symbol tables is part of the type checking phase of compilation. This is a pretty common misconception, that type constraints effect the parsing complexity of a language. Language type only relates to the process of building an abstract syntax tree from an input, not validating it.
    - munificent 10y ago
      > therefore parse-able as a regular language. You mean "context-free" not "regular" here, but either way, I believe that C is actually context-sensitive: (a)(b); Is this: 1. Evaluating "b" and casting it to type "a"? 2. Evaluating the parenthesized expression "a" which yields a function, and then calling it, passing in "b"? The only way to distinguish the two is by knowing whether "a" is a type or not. You could argue that as long as the parser produces a suitably vague AST, it doesn't need to know the distinction and can pass it on to later phases. I think that might work because I don't know of cases where the syntax actually diverges based on the type of a symbol. But in practice, I think most parsers want to produce a more precise AST that distinguishes cast expressions from function calls.
      - joshuata 10y ago
        You are right, the regular/context-free comment was a typo. You are also correct about c being non-context-free[0]. I have just seen many explanations of language hierarchy online mistaking type-checking for language complexity that it is a pet peeve of mine. [0] http://eli.thegreenplace.net/2007/11/24/the-context-sensitivity-of-cs-grammar http://eli.thegreenplace.net/2007/11/24/the-context-sensitiv...

How is it usually done in most high performance compilers, if I may ask?

nv-vn 10y ago

Parsed by hand

posterboy 10y ago
That strikes me as odd, but who am I to argue with the wisdom of the crowd. http://stackoverflow.com/questions/6319086/are-gcc-and-clang-parsers-really-handwritten http://stackoverflow.com/questions/6319086/are-gcc-and-clang... (short answer, yes)

lallysingh 10y ago

C++ is a context sensitive language, so (at least some) hand parsing is necessary.

munificent 10y ago
You can use a generated parser for C/C++, I believe. You just need to insert a little shim between the lexer and parser to look up identifiers in the symbol table and mark which name tokens refer to types versus functions or variables.
- joshuata 10y ago
  You are (essentially) correct. The language itself is context-free, and therefore parse-able as a regular language. Looking up identifiers in symbol tables is part of the type checking phase of compilation. This is a pretty common misconception, that type constraints effect the parsing complexity of a language. Language type only relates to the process of building an abstract syntax tree from an input, not validating it.
  - munificent 10y ago
    > therefore parse-able as a regular language. You mean "context-free" not "regular" here, but either way, I believe that C is actually context-sensitive: (a)(b); Is this: 1. Evaluating "b" and casting it to type "a"? 2. Evaluating the parenthesized expression "a" which yields a function, and then calling it, passing in "b"? The only way to distinguish the two is by knowing whether "a" is a type or not. You could argue that as long as the parser produces a suitably vague AST, it doesn't need to know the distinction and can pass it on to later phases. I think that might work because I don't know of cases where the syntax actually diverges based on the type of a symbol. But in practice, I think most parsers want to produce a more precise AST that distinguishes cast expressions from function calls.
    - joshuata 10y ago
      You are right, the regular/context-free comment was a typo. You are also correct about c being non-context-free[0]. I have just seen many explanations of language hierarchy online mistaking type-checking for language complexity that it is a pet peeve of mine. [0] http://eli.thegreenplace.net/2007/11/24/the-context-sensitivity-of-cs-grammar http://eli.thegreenplace.net/2007/11/24/the-context-sensitiv...