1

Is there any way to parse source string with custom (e)bnf and get AST as json? Let me explain what do i need:

  • I have source string and bnf grammar (as string too).
  • I put EBNF as lexer.
  • Add source.
  • Get AST and save it as JSON.
Paul Rumkin
  • 6,737
  • 2
  • 25
  • 35

1 Answers1

1

"EBNF as lexer" is nonsensical. But the rest of your question can be interpreted as, "can I get a parser driven by an EBNF to produce an AST in JSON form?"

Sure.

Most parser generators accept (E)BNF and "parse". Most of them don't automatically produce an AST; they make the programmer define how each rule should generate tree nodes. Those won't work for your task.

Some do generate ASTs as data structures automatically using just the BNF and a source file: ANTLR4 (I think), and our DMS Software Reengineering Toolkit. Neither of these produce JSON directly, but in both cases it should be straighforward to write (once) a generic tree-walker that spits JSON.

DMS's BNF will handle any context-free grammar using just BNF rules. ANTLR4 handles most grammars but has restrictions on what you can write (e.g., certain kinds of left recursion are verboten), and requirements for you to add extra disambiguating information where the grammar isn't LL(1).

DMS will export XML directly. See this example.

Community
  • 1
  • 1
Ira Baxter
  • 93,541
  • 22
  • 172
  • 341
  • So if i need to write tree-walker, then it make no sense which software to use, even YACC with C code. Am I right? – Paul Rumkin Nov 15 '13 at 12:27
  • Unless a miracle happens and somebody offers you package that does exactly what you specify (I know the parser world pretty well; I think there's little chance of this), you're not going to avoid doing some work. YACC is worse than ANTLR/DMS because it doesn't build trees for your grammar at all without significant help for you. The tree walker is pretty easy to build if you have an AST. If this isn't obvious to you, then I doubt you'll be able to use JSON result. – Ira Baxter Nov 15 '13 at 14:07
  • So and there is no software to convert source to flat list of lexems which could be used to build AST? – Paul Rumkin Nov 15 '13 at 14:17
  • That's not the question you asked. (My company happens to offer software that generates exactly such a list of lexemes for a number of widely used languages and easily for a "lexical bnf"). If you had such a thing, you still need a grammar to define what a parser will accept and to minimially define what an AST would look like, and you still need the machinery to build the AST to answer your original question (In our case, that's what DMS does). You appear to not want to do any work, and then you ask a question that requires more work to be done. What is your real goal? – Ira Baxter Nov 15 '13 at 16:59
  • My real goal is to solve the problem of converting several files with different syntax to one format as AST (or anythink else) that could be used in my program (to any purposes: highlighting, minimizing, stylizing, diff, etc). The solution i'm looking for should be portable and straightforward. I don't want to avoid any work, but i want to reduce it. – Paul Rumkin Nov 18 '13 at 06:51
  • DMS is a unified engine that parses many languages and produces ASTs using a uniform style. Writing out JSON is a trivial exercise. It appears to address all your needs, with perhaps "portability" being an exception; DMS is Windows-only (but will run on Linux) under Wine. There aren't any tools like it, with the exception of TXL and Stratego, which are less mature for this purpose (ANTLR4 being a distant 4th)... – Ira Baxter Nov 18 '13 at 09:50
  • ... The point of such tools is to minimize work required to manipulate source code in arbitrary ways; they include not just parse-to-AST machinery, but lots of other support for traversing/inspecting/modifying the ASTs in useful ways. You will find that the tasks you wish to do are more likely better done inside these tools, rather than exporting the ASTs to your tool, where you will have to duplicate all the additional AST manipulation machinery they already offer. – Ira Baxter Nov 18 '13 at 09:53