PEG: Difference between revisions

From Lojban
Jump to navigation Jump to search
m (Text replace - "jbocre: " to "")
m (Conversion script moved page PEG to pEG: Converting page titles to lowercase)

Revision as of 08:28, 30 June 2014

Parsing Expression grammars. Parsing expression grammars allow for full lookahead and backtracking in time linear to the input size. This makes them more expressive than YACC or BNF, which are limited in the how far they look ahead, and as a consequence how far they can backtrack. They also require more memory than either YACC or BNF to parse an equivalently sized input.

PEG grammars also do not have a separate lexing stage. Lexing and parsing are performed at the same time, using the same language for both.

See wikipedia for additional general information on arsing Expression Grammars.

4th Baseline Machine Grammar Proposal

.alyn.post. is working on a proposal for a 4th Machine Grammar Baseline, replacing the 3rd baseline's YACC grammar with a PEG grammar. This work is scheduled for inclusion into Suggestions for CLL, second edition LL version 2.0 or CLL Peg Errata LL version 2.1.

Morphology

Since PEG does not have a separate lexing stage, any PEG Machine Grammar will also need to express the Lojban Morphology in PEG.

Technical Points of the PEG language

  • The '.' characters means any character, in any character set. It is only used after fa'o, which unconditionally consumes the remaining characters.
  • '!.' is the way EOF is tested in PEG.
  • space is defined as the literal '.' (as opposed to the '.' operator of PEG), whitespace, and all punctuation other than ',' and .

CLL

The CLL will need to be updated to account for changes resulting from the translation of the grammar to PEG.

Main Article: CLL PEG Errata

Uncategorized Material

Open Discussion Points

  • jbogenturfa'i further transforms the PEG grammar into an idealized representation. This parse tree is suitable for programmatic manipulation. Why is this idealized parse tree not the way the PEG is written?

Lojban parsers that use PEG

See Also

  • YACC, the language in which Lojban's official grammar is defined.
  • BNF, widely considered easier to read than the YACC grammar.