3 ms·
If I understand it correctly, it demands to use simpler input languages, namely languages you can parse with a context-free grammar (in CS speak LL(k) or even b
by qznc 11y ago
If I understand it correctly, it demands to use simpler input languages, namely languages you can parse with a context-free grammar (in CS speak LL(k) or even better SLL(k)). To clarify, it is not about so much about how the programmers implements it (parser generator, combinator, or hand-coded), but more about what languages we specify.
Well, how many languages (or data formats) are SLL(k)? SQL is not, for example. A context-free grammar for SQL accepts "INSERT INTO example (a, b) VALUES ('test');". You need an additional check to find that you specify two columns to insert, but provide only one value.
This is common practice: Have a context-free grammar which accepts a superset of the actual language and filter it afterwards. Maybe you can fit the grammar more to the language, but it becomes quite ugly and big then. I don't think it is a good idea that we try to avoid the filter-afterwards and use big grammars, which we implement with shiny verification tools.
- TheLoneWolfling 11y agoHence: languages with a lexer pass followed by a parser pass.
- qznc 11y agoI was mostly talking about the semantic analysis pass after the parser pass. Type checking, name binding, etc. You are correct that the lexer pass allows you to expand a language despite the use of a context-free grammar in the parser. Significant whitespace lexed as indent/dedent tokens is a common example.