8 ms·

Langcc: A Next-Generation Compiler Compiler

177 points by mpweiher 4y ago

rurban 4y ago
Looks good, but I'm sceptical that I can specify perl5 or raku with it, as this would need dynamic flex rules. python, php or ruby should be fine though.
- KerrAvon 4y ago
  It includes a grammar for Python but says it has some limitations, so maybe, sort of. Amusingly, the included C grammar is shorter than the Python grammar. Ruby has some syntactical edge cases that make parsing a bit tricky.
  - defen 4y ago
    The C grammar is also not complete, so it doesn't necessarily mean anything that it's shorter than the Python one.
    - jzimmerman64 4y ago
      Correct. The C/C++ grammar is not complete; it only encodes the subset of the language that was needed to bootstrap langcc itself. As far as I am aware, however, the Python grammar parses the full industrial language Python 3.9.12.
      - defen 4y ago
        Do you think it would be possible to use this tool to create a full C frontend (including preprocessor)? I imagine the difficult part would be passing preprocessed text (including generated source e.g. pasted tokens, and expansion locations) into the C parser.
        jzimmerman64 4y ago
        The preprocessor would likely have to be a separate ad-hoc step, but it is possible that langcc could be used to generate a full C frontend if one is willing to run two passes (needed to deal with ambiguous cases such as "x * y", which can be either a multiplication expression or a variable declaration, depending on the contents of the symbol table).
- dontlaugh 4y ago
  Perl 5 is famously impossible to parse without executing, so no parser will be able to handle it.
  - rurban 4y ago
    That's not the point. flex is dynamic and can change the AST. langcc should also. perl5 uses a normal flex/bison parser setup.
benjaminjosephw 4y ago
> langcc is general enough that the tool is self-hosting: that is, one can express the "language of languages" in the "language of languages" itself There's something deeply satisfying about recursive tools who's inputs can include the definition of the tool itself. Brilliant.
- kragen 4y ago
  The OG of recursive parser generators whose inputs can include the definition of the parser generator itself is D. Val Schorre's META-II, which compiles itself (or other compilers written in the same grammar language) to an assembly language for a parsing-oriented abstract machine. Thanks to the ACM's enlightened policies, the META-II paper is now freely available (though not yet, as far as I can tell, open access): https://dl.acm.org/doi/10.1145/800257.808896 https://dl.acm.org/doi/10.1145/800257.808896 I wrote an improved version called Meta5ix http://canonical.org/~kragen/sw/dev3/meta5ix.m5 http://canonical.org/~kragen/sw/dev3/meta5ix.m5 (an interpreter for the virtual machine, with a complete description, is at http://canonical.org/~kragen/sw/dev3/meta5ixrun.py http://canonical.org/~kragen/sw/dev3/meta5ixrun.py, with the precompiled grammar at http://canonical.org/~kragen/sw/dev3/meta5ix.generated.m5asm http://canonical.org/~kragen/sw/dev3/meta5ix.generated.m5asm) and adapted it to produce C: http://canonical.org/~kragen/sw/dev3/meta5ix2c.m5 http://canonical.org/~kragen/sw/dev3/meta5ix2c.m5 (precompiled version at http://canonical.org/~kragen/sw/dev3/meta5ix2c.c http://canonical.org/~kragen/sw/dev3/meta5ix2c.c). Meta5ix written in itself is only 18 lines of code. Briefly, "" encloses expected input, {} encloses a line of output, [] encloses repeating constructs, commas separate alternatives (implemented without backtracking), fnord skips leading whitespace, $it copies the last <<>>-enclosed input token to the output, and other $variables interpolate locally-defined assembly labels. - program: ["-" name @it ":" terms {return}, "#" [:notin ""]] - terms: term ["," {continue $choice} term] @choice - term: (factor {else $seq}, output) [factor {assert}, output] @seq - factor: string {literal $it} , "(" terms ")" , "[" @many terms {continue $many} "]" , name {call $it} , "<<" {begin} terms ">>" {end} , ":fnord" {fnord} factor , ":notin" string {notin $it} , ":between" string {between $it} - output: (quasiquote, "@" {dedent} (var, quasiquote)) {writeline} - quasiquote: "{" [(<<ch [ch]>>, "\" <<:notin "">>) {say "$it"}, "$" var] "}" - ch: :notin "$}\" - var: "it" {copyinput}, name {gen $it} - string: :fnord <<'"' [:notin '"'] '"', "'" [:notin "'"] "'">> - name: :fnord <<letter [letter, :between "09"]>> - letter: :between "az", :between "AZ", :between "__" Meta5ix, like my earlier peg-bootstrap https://github.com/kragen/peg-bootstrap/blob/master/peg.md https://github.com/kragen/peg-bootstrap/blob/master/peg.md (66 lines of code, compiles to JavaScript, supports backtracking), is not really something you want to write a parser for your application language in. It's a compiler-compiler you can extend to support the parsing constructs you actually want for your language, then recompile with itself. Dave Long described META-II as "a field-improvised lever", and I think that's true of these as well, but maybe an even better analogy is Archimedes's fixed point.
duped 4y ago
Does it generate a batch or reactive compiler and allow for custom error recovery/messaging? It's always cool to see new tools but at a glance this doesn't seem to solve the problems that necessitate a hand written parser.
- sanxiyn 4y ago
  Just about all parser generators allow for custom error so this one does too. "Hand written parsers have better errors" is just an internet meme, not the actual state of the technology.
  - bsder 4y ago
    Is this really a meme? If so, I'd like a counterexample of a compiler that people regard as having actively good error messages that uses a parser generator. It seems like all the compilers I know of got much better errors when they switched to a fully custom generated intermediate language rather than one from a parser generator.
  - duped 4y ago
    ...so users write specific rules in their grammars for error cases and then add custom error messages? The actual state of the technology are tools like tree sitter, which doesn't generate an abstract syntax tree like this one does. I've written many parsers in my life. They're almost exclusively recursive descent because a generated parser is inferior in many, many ways. A lot of parser generators miss the forest for the trees - lexers are usually trivial to write and a hand rolled recursive descent parser takes about a day (and lets you handle precedence in a sane way that can be extensible!) - usually for better performance, easier maintainability, and good error handling. What's super hard to do is an incremental query oriented parser and compiler with a concrete syntax tree that doesn't use ungodly amounts of memory and has bad performance. Generative tools for that architecture are few and far between but much more useful than lex/yacc alternative.
jupp0r 4y ago
> automatically generates a compiler front-end For a very narrow definition of compiler frontend. The missing piece to make this super awesome would be generating LLVM IR, which is where the semantics of the language would need to be understood (vs just the grammar).
- tgv 4y ago
  Parser generator would be more apt.
  - jzimmerman64 4y ago
    It's not just a parser generator; it also generates the AST, traversals, lexer, and pretty-printer. And it can generate the AST for your IRs and target language, if you specify them in BNF as well. This is a pretty significant piece of a compiler, all told.
    - tgv 4y ago
      Generating the tree is trivial. The lexer is part of the parser. A pretty printer is not part of a compiler. The rest you have to do by hand. I know the name is a play on yacc (Yet Another Compiler Compiler), but it generates only a part of a compiler, the parser.
      - jzimmerman64 4y ago
        > Generating the tree is trivial. If by "generating the tree" you mean generating definitions for the AST data structures, this is nontrivial enough that yacc does not do it. > The lexer is part of the parser. Again, yacc (a parser generator) does not include a lexer generator; that requires a second package such as lex. > A pretty printer is not part of a compiler. A pretty-printer for the IR or target language is an important part of a compiler, as one needs to render the output in a form that some other tool (e.g., an assembler) can accept. A pretty-printer for the source language also comes in handy. > The rest you have to do by hand. What you have to do by hand is to write a function from the source AST to the target AST (i.e., a compiler backend). langcc generates the whole frontend, not just the parser.
npalli 4y ago
The linked paper is impressive on the golang and python implementations, possibly related to having a subset of features. “ The tool handles both languages automatically, and the generated code, when run on standard codebases, is 1.2x faster than the corresponding hand-written parser for Golang, and 4.3x faster than the CPython parser, respectively.”
- jzimmerman64 4y ago
  As far as we are aware, the grammars included with langcc (go.lang and py.lang) parse the full industrial programming languages Golang 1.17.8 and Python 3.9.12. They are not restricted subsets (even though cc.lang is a restricted subset of C++).
  - npalli 4y ago
    Thank you, that's impressive. Good work.
ridiculous_fish 4y ago
Some questions I have 1. Is there support for comments beyond just the lexer, e.g. attaching them to nodes for a source beautifier? 2. Is there support for parsing incomplete input? I got it building, should anyone be curious about the generated source I posted it here for the "calc" example: Header file: https://gist.github.com/ridiculousfish/63449ca95d3f957f53a85b2c3e115378 https://gist.github.com/ridiculousfish/63449ca95d3f957f53a85... .cpp file: https://gist.github.com/ridiculousfish/32b053325b698adda782fdbad7a20d6d https://gist.github.com/ridiculousfish/32b053325b698adda782f...
armchairhacker 4y ago
The auto-generated AST data structures are really the selling point here. Having to manually write an AST for your language and update it if you update your language is mechanical and tedious. I suggest the developer also look into auto-generated visitor / traversal functions as well, as those are also very mechanical and tedious. Another suggestion is to make sure the grammar preserves source information (file, line, column span) and implement re-printing which preserves comments and whitespace in unmodified sections of the AST. I get those are a lot of work though, as-is this is very impressive.
- mhh__ 4y ago
  Auto generating stuff also forces you to not bolt tons of shit into all the last nodes
- jzimmerman64 4y ago
  > I suggest the developer also look into auto-generated visitor / traversal functions as well In fact, langcc already has visitor/traversal functions, though they are not so well documented yet. I have just added an example (expr_simpl in https://github.com/jzimmerman/langcc/blob/main/examples/calc/calc_main.cpp https://github.com/jzimmerman/langcc/blob/main/examples/calc...). > Another suggestion is to make sure the grammar preserves source information (file, line, column span) This is already present as well (the calc example illustrates this functionality). > implement re-printing which preserves comments and whitespace I considered doing this, but it's surprisingly difficult to get the specification right, especially in whitespace-sensitive languages like Python.
- layer8 4y ago
  I don’t find this to be very impressive. I used SableCC [0] 15 years ago, which generates Java source code (classes) for the AST along with the parser, including Visitor traversal. It was missing line number information and character data between tokens, but that was straightforward to add by modifying the built-in templates used to generate the AST classes. I was also able to add generically-typed return values to the Visitor mechanism just by editing the built-in templates. [0] https://sablecc.org/ https://sablecc.org/
- 4y ago
lalaithion 4y ago
Some questions it would be great to feature in the README: - How are the error messages? - Does it produce source spans for intermediate AST nodes? - Can it handle operator precedence without encoding the precedence into the grammar? - Can it handle source-code-defined operator precedence?
- jzimmerman64 4y ago
  The README is a work in progress, but some of these answers can be found in the documentation (https://arxiv.org/abs/2209.08385 https://arxiv.org/abs/2209.08385). In particular: > How are the error messages? langcc produces "confusing input pairs" for LR conflicts, which enable the user to pinpoint the cause of the error much more easily than the opaque shift/reduce errors in tools such as yacc/bison. > Does it produce source spans for intermediate AST nodes? Yes! You can find an example in https://github.com/jzimmerman/langcc/blob/main/examples/calc/calc_main.cpp https://github.com/jzimmerman/langcc/blob/main/examples/calc.... > Can it handle operator precedence without encoding the precedence into the grammar? Yes - detailed in the documentation. > Can it handle source-code-defined operator precedence? Depends on what you mean by source-code-defined. The operations supported by langcc's precedence stanzas (detailed in the documentation) are quite comprehensive, and suffice to encode the operator precedence rules in Golang 1.17.8, for example.
  - lalaithion 4y ago
    Thanks! In general, I would avoid putting the documentation for a programming tool in a pdf hosted on Arxiv. It didn’t even occur to me that either of those links would be useful documentation. Additionally, pdf form isn’t the most helpful way to present documentation either.
    - mdaniel 4y ago
      See if you find this easier to read: https://github.com/mdaniel/langcc/blob/documentation/2209.08385.adoc https://github.com/mdaniel/langcc/blob/documentation/2209.08...
pabs3 4y ago
This might be useful for bootstrapping languages from other languages. https://bootstrappable.org/ https://bootstrappable.org/
Darmani 4y ago
I have not published any papers on parsing, but I've read a large chunk of the Handbook on Parsing, am buddies with Terrence Parr and have given a lecture on the ALL() parsing algorithm, and worked for a company that has perhaps the most extensive collection of GLR parsers around. (Whereas langcc boasts automatically-generated parsers for the easy-to-parse Python and Go, my old employer has automatically-generated parsers for Ruby, C++, COBOL, and about 100 others.) I would not consider myself an expert on parsing in comparison to the few who research it, but I would consider myself expert by the standards of most professional compiler engineers, and certainly by the standards of the average software engineer. When I see a library like this, I ask "What new things does this thing bring to the table?" For that, before I even get into trying to understand what it does, I want to see how well the author understands what's already been done and how it compares to prior work. My very blunt assessment: I don't see any reason to take this library seriously. I looked at the 40 page paper. I can tell just from the citations that it takes a very 70's few of parsing. And when it does discuss other work, it mostly gets it wrong. A few examples: Page 8: He writes about the "ETL family, also called GLR parsing." "ETL family" seems to be a term of his own coinage, and he's writing about GLR parsing and Earley parsing as if they're the same. Now that I think about it, I see some resemblance, but they're usually considered quite different. See e.g.: https://cstheory.stackexchange.com/questions/30903/why-tomita-created-glr-and-didnt-use-earley https://cstheory.stackexchange.com/questions/30903/why-tomit... * Page 9 > There has also been significant development of the top-down family of parser generators, including tools such as ANTLR [PQ95] which support a superset of LL(k) grammars, as well as their parallel counterparts, referred to as Generalized LL (GLL). For the reasons described above, we believe that while top-down parsers are theoretically interesting, the grammars they support are not sufficiently general to capture full programming languages.6 Notably, they are significantly more restrictive than LR(k), and we argue that even the latter is not sufficiently general in its standard formulation. This has not been true since ANTLR 2, released 25 years ago. The LL() algorithm of ANTLR 3, described in a 2011 publication, is capable of parsing even some context-sensitive grammars. Page 9: > The tree automata of Adams and Might [AM17] are similar to our implementation of monotonic attributes; they differ in that they impose left-to-right sequencing on the attribute constraints (whereas attributes can refer to arbitrary constituents of a grammar rule), and require productions to be duplicated (whereas attributes are boolean or integer values layered independently on top of the standard context-free grammar rules)." This is one of my favorite papers of the last 5 years, and this is totally inaccurate. The user writes down a normal grammar and syntactic regular expressions for forbidden subterms. From that, it automatically generates a new grammar that e.g.: breaks symmetries. In short, I think the author has the knowledge to claim that his solution beats the best that the 70's and 80's has to offer. I am not motivated to look at this any further because I've been given no reason to believe it's had a fair comparison to what the 2010's has to offer. I continue to recommend ANTLR 4 for your parser-generator needs. Its ALL(*) algorithm truly is magic. tree-sitter is also good and has a lot of momentum. Joe Zimmerman: If you're reading this, please don't take it too personally. I'm reacting to the claims of the work more than the work itself. If you'd like, I'll gladly discuss this with you. Either I'll learn something new, you'll get better at clarifying your ideas, or both.
the_duke 4y ago
There's a lot of focus on parsing and AST definition in the language space. It's true that both of those are a bit tedious to write, but in reality they represent a tiny amount of the work that goes into writing a language. It's nice for experimentation, but you will soon need to customise your AST, add interning, have a permissive parser with error recovery (which always depends on language semantics) , propagate errors through your AST, ... Most people who try to implement a language never get beyond the parse code to AST stage, so this would be nice for students and beginners. But I don't think it's impactful beyond that.
- jzimmerman64 4y ago
  Many of these claims are subjective, but I will at least point out one fact: langcc is general enough to compile its own frontend - and not just for experimentation.
mingodad 4y ago
It seems too hack depending on "__attribute__((always_inline))", tcmalloc for performance, specific libunwind to dump backtraces, doesn't build with g++. Maybe the general idea is valuable but the implementation ?
HarHarVeryFunny 4y ago
Meh .. I wrote a full LR(1) parser generator for fun about 40 years ago (c.1982), back when it was considered impossibly impractical (the "dragon book" said so!). Generating an LR(1) parser itself is simple enough using Knuth's algorithm - you're just building a large state machine and having to maintain sets of look-head tokens for each partially-parsed production rule in the states, which is why the resulting state machine becomes impractically large (at least for computers at that time). What made this possible back at that time was a paper by Professor Pager from the university of Hawaii that described how you could merge states, under certain compatibility conditions, during the cannonical Knuth parser (state machine) generation algorithm, which kept the size of the state machine under control. The parsers built by parser generators like mine, YACC, OP's Langcc, etc, are referred to as "table driven parsers" (to differentiate them from recursive descent parsers), but back in 1982 representing the state machine as an actual table wasn't very practical (too big) so rather than having a large sparse 2-D array indexed by state and token you'd normally represent each state as a list of actions instead. However, I found I could represent the tables an sparse 2-D array, but then compress the array to make it on manageable size. This was much preferable to using lists since access was much faster - just 3 array accesses to translate raw state, token indeces into compressed array indeces, then the actual lookup. To compress the sparse array I converted it into a graph coloring problem. I mapped the sparse array to a graph where each row of the array would map to a node in the graph, and any two nodes would be connected only if the corresponding sparse rows had a conflicting entry in any column. I then used a simple graph coloring heuristic to color the graph (goal - color graph with minimum number of colors, given constraint that connected nodes can't have the same color), then converted back to a compressed array by merging rows whose corresponding graph node's had the same color (hence no conflicts). I then repeated same procedure for the columns. The resulting parsers, when coupled with an optimized hand written tokenizer, was stunningly fast, even on the dog slow computers of the time, but sadly I never did anything with it - was just a fun side project done for my own education/amusement. The good old days. Get off my lawn.
- jzimmerman64 4y ago
  > back when it was considered impossibly impractical (the "dragon book" said so!) Yes, with some optimizations (e.g., Pager's algorithm), LR(1) can be practical; in langcc we even implement LR(k), and this is also practical for many real-world grammars. However, a key observation is that even LR(k) is not enough for many industrial language features. You may enjoy reading the companion technical report for langcc, which delves deep into the underlying parsing theory and proposes a number of new techniques: https://arxiv.org/pdf/2209.08383.pdf https://arxiv.org/pdf/2209.08383.pdf
jzimmerman64 4y ago
Readers who are interested in parsing theory may also enjoy the companion technical report: https://arxiv.org/pdf/2209.08383.pdf https://arxiv.org/pdf/2209.08383.pdf as well as a brief users' manual, available here: https://arxiv.org/pdf/2209.08385.pdf https://arxiv.org/pdf/2209.08385.pdf

177 points by mpweiher 4y ago

Looks good, but I'm sceptical that I can specify perl5 or raku with it, as this would need dynamic flex rules. python, php or ruby should be fine though.

KerrAvon 4y ago
It includes a grammar for Python but says it has some limitations, so maybe, sort of. Amusingly, the included C grammar is shorter than the Python grammar. Ruby has some syntactical edge cases that make parsing a bit tricky.
- defen 4y ago
  The C grammar is also not complete, so it doesn't necessarily mean anything that it's shorter than the Python one.
  - jzimmerman64 4y ago
    Correct. The C/C++ grammar is not complete; it only encodes the subset of the language that was needed to bootstrap langcc itself. As far as I am aware, however, the Python grammar parses the full industrial language Python 3.9.12.
    - defen 4y ago
      Do you think it would be possible to use this tool to create a full C frontend (including preprocessor)? I imagine the difficult part would be passing preprocessed text (including generated source e.g. pasted tokens, and expansion locations) into the C parser.
      - jzimmerman64 4y ago
        The preprocessor would likely have to be a separate ad-hoc step, but it is possible that langcc could be used to generate a full C frontend if one is willing to run two passes (needed to deal with ambiguous cases such as "x * y", which can be either a multiplication expression or a variable declaration, depending on the contents of the symbol table).
dontlaugh 4y ago
Perl 5 is famously impossible to parse without executing, so no parser will be able to handle it.
- rurban 4y ago
  That's not the point. flex is dynamic and can change the AST. langcc should also. perl5 uses a normal flex/bison parser setup.

benjaminjosephw 4y ago

> langcc is general enough that the tool is self-hosting: that is, one can express the "language of languages" in the "language of languages" itself There's something deeply satisfying about recursive tools who's inputs can include the definition of the tool itself. Brilliant.

kragen 4y ago
The OG of recursive parser generators whose inputs can include the definition of the parser generator itself is D. Val Schorre's META-II, which compiles itself (or other compilers written in the same grammar language) to an assembly language for a parsing-oriented abstract machine. Thanks to the ACM's enlightened policies, the META-II paper is now freely available (though not yet, as far as I can tell, open access): https://dl.acm.org/doi/10.1145/800257.808896 https://dl.acm.org/doi/10.1145/800257.808896 I wrote an improved version called Meta5ix http://canonical.org/~kragen/sw/dev3/meta5ix.m5 http://canonical.org/~kragen/sw/dev3/meta5ix.m5 (an interpreter for the virtual machine, with a complete description, is at http://canonical.org/~kragen/sw/dev3/meta5ixrun.py http://canonical.org/~kragen/sw/dev3/meta5ixrun.py, with the precompiled grammar at http://canonical.org/~kragen/sw/dev3/meta5ix.generated.m5asm http://canonical.org/~kragen/sw/dev3/meta5ix.generated.m5asm) and adapted it to produce C: http://canonical.org/~kragen/sw/dev3/meta5ix2c.m5 http://canonical.org/~kragen/sw/dev3/meta5ix2c.m5 (precompiled version at http://canonical.org/~kragen/sw/dev3/meta5ix2c.c http://canonical.org/~kragen/sw/dev3/meta5ix2c.c). Meta5ix written in itself is only 18 lines of code. Briefly, "" encloses expected input, {} encloses a line of output, [] encloses repeating constructs, commas separate alternatives (implemented without backtracking), fnord skips leading whitespace, $it copies the last <<>>-enclosed input token to the output, and other $variables interpolate locally-defined assembly labels. - program: ["-" name @it ":" terms {return}, "#" [:notin ""]] - terms: term ["," {continue $choice} term] @choice - term: (factor {else $seq}, output) [factor {assert}, output] @seq - factor: string {literal $it} , "(" terms ")" , "[" @many terms {continue $many} "]" , name {call $it} , "<<" {begin} terms ">>" {end} , ":fnord" {fnord} factor , ":notin" string {notin $it} , ":between" string {between $it} - output: (quasiquote, "@" {dedent} (var, quasiquote)) {writeline} - quasiquote: "{" [(<<ch [ch]>>, "\" <<:notin "">>) {say "$it"}, "$" var] "}" - ch: :notin "$}\" - var: "it" {copyinput}, name {gen $it} - string: :fnord <<'"' [:notin '"'] '"', "'" [:notin "'"] "'">> - name: :fnord <<letter [letter, :between "09"]>> - letter: :between "az", :between "AZ", :between "__" Meta5ix, like my earlier peg-bootstrap https://github.com/kragen/peg-bootstrap/blob/master/peg.md https://github.com/kragen/peg-bootstrap/blob/master/peg.md (66 lines of code, compiles to JavaScript, supports backtracking), is not really something you want to write a parser for your application language in. It's a compiler-compiler you can extend to support the parsing constructs you actually want for your language, then recompile with itself. Dave Long described META-II as "a field-improvised lever", and I think that's true of these as well, but maybe an even better analogy is Archimedes's fixed point.

duped 4y ago

Does it generate a batch or reactive compiler and allow for custom error recovery/messaging? It's always cool to see new tools but at a glance this doesn't seem to solve the problems that necessitate a hand written parser.

sanxiyn 4y ago
Just about all parser generators allow for custom error so this one does too. "Hand written parsers have better errors" is just an internet meme, not the actual state of the technology.
- bsder 4y ago
  Is this really a meme? If so, I'd like a counterexample of a compiler that people regard as having actively good error messages that uses a parser generator. It seems like all the compilers I know of got much better errors when they switched to a fully custom generated intermediate language rather than one from a parser generator.
- duped 4y ago
  ...so users write specific rules in their grammars for error cases and then add custom error messages? The actual state of the technology are tools like tree sitter, which doesn't generate an abstract syntax tree like this one does. I've written many parsers in my life. They're almost exclusively recursive descent because a generated parser is inferior in many, many ways. A lot of parser generators miss the forest for the trees - lexers are usually trivial to write and a hand rolled recursive descent parser takes about a day (and lets you handle precedence in a sane way that can be extensible!) - usually for better performance, easier maintainability, and good error handling. What's super hard to do is an incremental query oriented parser and compiler with a concrete syntax tree that doesn't use ungodly amounts of memory and has bad performance. Generative tools for that architecture are few and far between but much more useful than lex/yacc alternative.

jupp0r 4y ago

> automatically generates a compiler front-end For a very narrow definition of compiler frontend. The missing piece to make this super awesome would be generating LLVM IR, which is where the semantics of the language would need to be understood (vs just the grammar).

tgv 4y ago
Parser generator would be more apt.
- jzimmerman64 4y ago
  It's not just a parser generator; it also generates the AST, traversals, lexer, and pretty-printer. And it can generate the AST for your IRs and target language, if you specify them in BNF as well. This is a pretty significant piece of a compiler, all told.
  - tgv 4y ago
    Generating the tree is trivial. The lexer is part of the parser. A pretty printer is not part of a compiler. The rest you have to do by hand. I know the name is a play on yacc (Yet Another Compiler Compiler), but it generates only a part of a compiler, the parser.
    - jzimmerman64 4y ago
      > Generating the tree is trivial. If by "generating the tree" you mean generating definitions for the AST data structures, this is nontrivial enough that yacc does not do it. > The lexer is part of the parser. Again, yacc (a parser generator) does not include a lexer generator; that requires a second package such as lex. > A pretty printer is not part of a compiler. A pretty-printer for the IR or target language is an important part of a compiler, as one needs to render the output in a form that some other tool (e.g., an assembler) can accept. A pretty-printer for the source language also comes in handy. > The rest you have to do by hand. What you have to do by hand is to write a function from the source AST to the target AST (i.e., a compiler backend). langcc generates the whole frontend, not just the parser.

npalli 4y ago

The linked paper is impressive on the golang and python implementations, possibly related to having a subset of features. “ The tool handles both languages automatically, and the generated code, when run on standard codebases, is 1.2x faster than the corresponding hand-written parser for Golang, and 4.3x faster than the CPython parser, respectively.”

jzimmerman64 4y ago
As far as we are aware, the grammars included with langcc (go.lang and py.lang) parse the full industrial programming languages Golang 1.17.8 and Python 3.9.12. They are not restricted subsets (even though cc.lang is a restricted subset of C++).
- npalli 4y ago
  Thank you, that's impressive. Good work.

ridiculous_fish 4y ago

Some questions I have 1. Is there support for comments beyond just the lexer, e.g. attaching them to nodes for a source beautifier? 2. Is there support for parsing incomplete input? I got it building, should anyone be curious about the generated source I posted it here for the "calc" example: Header file: https://gist.github.com/ridiculousfish/63449ca95d3f957f53a85b2c3e115378 https://gist.github.com/ridiculousfish/63449ca95d3f957f53a85... .cpp file: https://gist.github.com/ridiculousfish/32b053325b698adda782fdbad7a20d6d https://gist.github.com/ridiculousfish/32b053325b698adda782f...

armchairhacker 4y ago

The auto-generated AST data structures are really the selling point here. Having to manually write an AST for your language and update it if you update your language is mechanical and tedious. I suggest the developer also look into auto-generated visitor / traversal functions as well, as those are also very mechanical and tedious. Another suggestion is to make sure the grammar preserves source information (file, line, column span) and implement re-printing which preserves comments and whitespace in unmodified sections of the AST. I get those are a lot of work though, as-is this is very impressive.

mhh__ 4y ago
Auto generating stuff also forces you to not bolt tons of shit into all the last nodes
jzimmerman64 4y ago
> I suggest the developer also look into auto-generated visitor / traversal functions as well In fact, langcc already has visitor/traversal functions, though they are not so well documented yet. I have just added an example (expr_simpl in https://github.com/jzimmerman/langcc/blob/main/examples/calc/calc_main.cpp https://github.com/jzimmerman/langcc/blob/main/examples/calc...). > Another suggestion is to make sure the grammar preserves source information (file, line, column span) This is already present as well (the calc example illustrates this functionality). > implement re-printing which preserves comments and whitespace I considered doing this, but it's surprisingly difficult to get the specification right, especially in whitespace-sensitive languages like Python.
layer8 4y ago
I don’t find this to be very impressive. I used SableCC [0] 15 years ago, which generates Java source code (classes) for the AST along with the parser, including Visitor traversal. It was missing line number information and character data between tokens, but that was straightforward to add by modifying the built-in templates used to generate the AST classes. I was also able to add generically-typed return values to the Visitor mechanism just by editing the built-in templates. [0] https://sablecc.org/ https://sablecc.org/
4y ago

lalaithion 4y ago

Some questions it would be great to feature in the README: - How are the error messages? - Does it produce source spans for intermediate AST nodes? - Can it handle operator precedence without encoding the precedence into the grammar? - Can it handle source-code-defined operator precedence?

jzimmerman64 4y ago
The README is a work in progress, but some of these answers can be found in the documentation (https://arxiv.org/abs/2209.08385 https://arxiv.org/abs/2209.08385). In particular: > How are the error messages? langcc produces "confusing input pairs" for LR conflicts, which enable the user to pinpoint the cause of the error much more easily than the opaque shift/reduce errors in tools such as yacc/bison. > Does it produce source spans for intermediate AST nodes? Yes! You can find an example in https://github.com/jzimmerman/langcc/blob/main/examples/calc/calc_main.cpp https://github.com/jzimmerman/langcc/blob/main/examples/calc.... > Can it handle operator precedence without encoding the precedence into the grammar? Yes - detailed in the documentation. > Can it handle source-code-defined operator precedence? Depends on what you mean by source-code-defined. The operations supported by langcc's precedence stanzas (detailed in the documentation) are quite comprehensive, and suffice to encode the operator precedence rules in Golang 1.17.8, for example.
- lalaithion 4y ago
  Thanks! In general, I would avoid putting the documentation for a programming tool in a pdf hosted on Arxiv. It didn’t even occur to me that either of those links would be useful documentation. Additionally, pdf form isn’t the most helpful way to present documentation either.
  - mdaniel 4y ago
    See if you find this easier to read: https://github.com/mdaniel/langcc/blob/documentation/2209.08385.adoc https://github.com/mdaniel/langcc/blob/documentation/2209.08...

pabs3 4y ago

This might be useful for bootstrapping languages from other languages. https://bootstrappable.org/ https://bootstrappable.org/

Darmani 4y ago

I have not published any papers on parsing, but I've read a large chunk of the Handbook on Parsing, am buddies with Terrence Parr and have given a lecture on the ALL() parsing algorithm, and worked for a company that has perhaps the most extensive collection of GLR parsers around. (Whereas langcc boasts automatically-generated parsers for the easy-to-parse Python and Go, my old employer has automatically-generated parsers for Ruby, C++, COBOL, and about 100 others.) I would not consider myself an expert on parsing in comparison to the few who research it, but I would consider myself expert by the standards of most professional compiler engineers, and certainly by the standards of the average software engineer. When I see a library like this, I ask "What new things does this thing bring to the table?" For that, before I even get into trying to understand what it does, I want to see how well the author understands what's already been done and how it compares to prior work. My very blunt assessment: I don't see any reason to take this library seriously. I looked at the 40 page paper. I can tell just from the citations that it takes a very 70's few of parsing. And when it does discuss other work, it mostly gets it wrong. A few examples: Page 8: He writes about the "ETL family, also called GLR parsing." "ETL family" seems to be a term of his own coinage, and he's writing about GLR parsing and Earley parsing as if they're the same. Now that I think about it, I see some resemblance, but they're usually considered quite different. See e.g.: https://cstheory.stackexchange.com/questions/30903/why-tomita-created-glr-and-didnt-use-earley https://cstheory.stackexchange.com/questions/30903/why-tomit... * Page 9 > There has also been significant development of the top-down family of parser generators, including tools such as ANTLR [PQ95] which support a superset of LL(k) grammars, as well as their parallel counterparts, referred to as Generalized LL (GLL). For the reasons described above, we believe that while top-down parsers are theoretically interesting, the grammars they support are not sufficiently general to capture full programming languages.6 Notably, they are significantly more restrictive than LR(k), and we argue that even the latter is not sufficiently general in its standard formulation. This has not been true since ANTLR 2, released 25 years ago. The LL() algorithm of ANTLR 3, described in a 2011 publication, is capable of parsing even some context-sensitive grammars. Page 9: > The tree automata of Adams and Might [AM17] are similar to our implementation of monotonic attributes; they differ in that they impose left-to-right sequencing on the attribute constraints (whereas attributes can refer to arbitrary constituents of a grammar rule), and require productions to be duplicated (whereas attributes are boolean or integer values layered independently on top of the standard context-free grammar rules)." This is one of my favorite papers of the last 5 years, and this is totally inaccurate. The user writes down a normal grammar and syntactic regular expressions for forbidden subterms. From that, it automatically generates a new grammar that e.g.: breaks symmetries. In short, I think the author has the knowledge to claim that his solution beats the best that the 70's and 80's has to offer. I am not motivated to look at this any further because I've been given no reason to believe it's had a fair comparison to what the 2010's has to offer. I continue to recommend ANTLR 4 for your parser-generator needs. Its ALL(*) algorithm truly is magic. tree-sitter is also good and has a lot of momentum. Joe Zimmerman: If you're reading this, please don't take it too personally. I'm reacting to the claims of the work more than the work itself. If you'd like, I'll gladly discuss this with you. Either I'll learn something new, you'll get better at clarifying your ideas, or both.

the_duke 4y ago

There's a lot of focus on parsing and AST definition in the language space. It's true that both of those are a bit tedious to write, but in reality they represent a tiny amount of the work that goes into writing a language. It's nice for experimentation, but you will soon need to customise your AST, add interning, have a permissive parser with error recovery (which always depends on language semantics) , propagate errors through your AST, ... Most people who try to implement a language never get beyond the parse code to AST stage, so this would be nice for students and beginners. But I don't think it's impactful beyond that.

jzimmerman64 4y ago
Many of these claims are subjective, but I will at least point out one fact: langcc is general enough to compile its own frontend - and not just for experimentation.

mingodad 4y ago

It seems too hack depending on "__attribute__((always_inline))", tcmalloc for performance, specific libunwind to dump backtraces, doesn't build with g++. Maybe the general idea is valuable but the implementation ?

HarHarVeryFunny 4y ago

Meh .. I wrote a full LR(1) parser generator for fun about 40 years ago (c.1982), back when it was considered impossibly impractical (the "dragon book" said so!). Generating an LR(1) parser itself is simple enough using Knuth's algorithm - you're just building a large state machine and having to maintain sets of look-head tokens for each partially-parsed production rule in the states, which is why the resulting state machine becomes impractically large (at least for computers at that time). What made this possible back at that time was a paper by Professor Pager from the university of Hawaii that described how you could merge states, under certain compatibility conditions, during the cannonical Knuth parser (state machine) generation algorithm, which kept the size of the state machine under control. The parsers built by parser generators like mine, YACC, OP's Langcc, etc, are referred to as "table driven parsers" (to differentiate them from recursive descent parsers), but back in 1982 representing the state machine as an actual table wasn't very practical (too big) so rather than having a large sparse 2-D array indexed by state and token you'd normally represent each state as a list of actions instead. However, I found I could represent the tables an sparse 2-D array, but then compress the array to make it on manageable size. This was much preferable to using lists since access was much faster - just 3 array accesses to translate raw state, token indeces into compressed array indeces, then the actual lookup. To compress the sparse array I converted it into a graph coloring problem. I mapped the sparse array to a graph where each row of the array would map to a node in the graph, and any two nodes would be connected only if the corresponding sparse rows had a conflicting entry in any column. I then used a simple graph coloring heuristic to color the graph (goal - color graph with minimum number of colors, given constraint that connected nodes can't have the same color), then converted back to a compressed array by merging rows whose corresponding graph node's had the same color (hence no conflicts). I then repeated same procedure for the columns. The resulting parsers, when coupled with an optimized hand written tokenizer, was stunningly fast, even on the dog slow computers of the time, but sadly I never did anything with it - was just a fun side project done for my own education/amusement. The good old days. Get off my lawn.

jzimmerman64 4y ago
> back when it was considered impossibly impractical (the "dragon book" said so!) Yes, with some optimizations (e.g., Pager's algorithm), LR(1) can be practical; in langcc we even implement LR(k), and this is also practical for many real-world grammars. However, a key observation is that even LR(k) is not enough for many industrial language features. You may enjoy reading the companion technical report for langcc, which delves deep into the underlying parsing theory and proposes a number of new techniques: https://arxiv.org/pdf/2209.08383.pdf https://arxiv.org/pdf/2209.08383.pdf

jzimmerman64 4y ago

Readers who are interested in parsing theory may also enjoy the companion technical report: https://arxiv.org/pdf/2209.08383.pdf https://arxiv.org/pdf/2209.08383.pdf as well as a brief users' manual, available here: https://arxiv.org/pdf/2209.08385.pdf https://arxiv.org/pdf/2209.08385.pdf