SYNTAX
SYNTAX is a system used to generate the lexical and syntactic analyzers, the parsers, that let a computer make sense of structured text. It was built at INRIA in France, and for several decades much of that work fell to a single person: Pierre Boullier. For years it stayed inside the institute. Only in 2007 did it become free software, released under the CeCILL license. What does it actually take to teach a machine to read a grammar? Why would the same tool serve both a programming compiler and the analysis of human language? And how does a parser pick itself back up when the input it receives is broken?
Context-free grammars, or CFGs, sit at the heart of what SYNTAX was designed to handle. The system generates analyzers for all kinds of context-free grammars, and it reaches further still into some classes of contextual grammars. It produces both deterministic and non-deterministic analyzers, so a single tool covers grammars that resolve cleanly and grammars that branch into ambiguity. That breadth is unusual. Most parser tools commit to one mode of reading, while SYNTAX spans the range from tightly unambiguous rules to open-ended structures.
LR, LALR, and RLR grammars fall within the deterministic, unambiguous classes that SYNTAX manages, alongside general context-free grammars. The deterministic version has been used in operational settings, including Ada, and continues to be used in the domain of compilation. On the non-deterministic side, SYNTAX provides an Earley parser generator, a tool aimed at natural language processing. The parsers it generates can run semantic actions and evaluate attributes, working either on the abstract tree or on the shared parse forest. That shared parse forest is what allows the system to hold many possible readings at once.
Version 6.0 beta of SYNTAX carries the tool past compilers and into formalisms that no programming language ever needed. This release includes parser generators for context-sensitive formalisms, serving natural language processing and bio-informatics alike. Among them are TAG and RCG, formalisms built to capture structures that plain context-free rules cannot.
LFG marks the other path SYNTAX takes into language analysis. Here the approach leans on context-free grammars and then extends them through attribute evaluation, a technique aimed in particular at natural language processing. The same engine that once helped compile Ada now reaches into the messy grammar of human sentences and the structures studied in bio-informatics.
Lex and Yacc, the familiar names in this space, do not do what SYNTAX does when a parse goes wrong. SYNTAX carries a built-in algorithm for automatically recovering from lexical and syntactic errors. It can delete extra characters or tokens, insert missing ones, or permute characters and tokens to get back on track. Rather than halt at the first mistake, the parser keeps reading.
The recovery algorithm ships with a default behaviour, but it does not have to stay that way. A developer can supply a custom set of recovery rules tuned to the specific language the lexer and parser were built for. That customization is what lets a general tool fit a particular grammar's quirks, the same flexibility that carried SYNTAX from the compilation of Ada to the parsing of natural language.
Common questions
What is SYNTAX in computer science?
SYNTAX is a system used to generate lexical and syntactic analyzers, also called parsers, for all kinds of context-free grammars as well as some classes of contextual grammars. It produces both deterministic and non-deterministic analyzers.
Who developed the SYNTAX parser system and where?
SYNTAX was developed at INRIA in France over several decades, mostly by Pierre Boullier.
When did SYNTAX become free software and under what license?
SYNTAX became free software in 2007 and is distributed under the CeCILL license.
What grammar types does SYNTAX support?
SYNTAX handles deterministic, unambiguous grammars such as LR, LALR, and RLR, along with general context-free grammars. Its non-deterministic features include an Earley parser generator used for natural language processing.
How does SYNTAX recover from parsing errors?
SYNTAX includes a built-in algorithm that automatically recovers from lexical and syntactic errors by deleting extra characters or tokens, inserting missing ones, or permuting characters or tokens. Its default behaviour can be modified with a custom set of recovery rules adapted to the target language.
What is SYNTAX used for beyond compilation?
Beyond the domain of compilation, where its deterministic version has been used in operational contexts such as Ada, SYNTAX version 6.0 beta includes parser generators for context-sensitive formalisms such as TAG, RCG, and LFG, used for natural language processing and bio-informatics.