CODEWITHSUNDEEP
phpparsingbnfebnf
XTRUST.ORG
XTRUST.ORG

Reputation: 3402

Convert EBNF grammar to PEG

I have an EBNF grammar and want to convert it to PEG (https://github.com/anatoo/PHPPEG):

query = { word | wildcard }
word = ( [apostrophe] ( letter { alpha } ) ) | ” , ”
letter = ” a ” | ... | ” z ” | ” A ” | ... | ” Z ”
alpha = letter | ” 0 ” | ... | ” 9 ”
apostrophe = ” ’ ”
wildcard = ” ? ” | ” * ” | synonyms | multiset | optionset
synonyms = ” ~ ” word
multiset = ” { ” word { word } ” } ”
optionset = ” [ ” word { word } ” ] ”

Can anyone explain how to convert from one to another, or if there's somewhere where I can read about it?

Thanks!

• the question mark (?), which matches exactly one word;
• the asterisk (*), which matches any sequence of words;
• the tilde sign in front of a word (∼<word>), which matches any of the word’s synonyms;
• the multiset operator ({<words>}), which matches any ordering of the enumerated words; and,
• the optionset operator ([<words>]), which matches any one word from a list of options.

Upvotes: 6

Views: 1585

Answers (1)

Branco Medeiros
Branco Medeiros

Reputation: 759

There are several Peg implementations, and all of then add something to the general conventions addopted by Peg, which are:

  • The operators "*", "+" and "?" have the same meaning as in regular expressions;
  • Alternatives are actually priority choices, and they use the "/" operator to indicate that difference;
  • The operators "&" and "!" designate positive and negative zero-length lookahead (i.e. they don't advance the 'current' pointer);

In EBNF repetition is represented by "{ }", which in Peg is represented by the "*" operator, meaning zero or more repetitions of the subject. As an example, your first grammar rule could be represented as follows in an hypothetical Peg implementation:

query = (word / wildcard)*

The EBNF "[ ]" operator has the same meaning as Peg's "?" operator, meaning that the subject is optional. Here is your second rule as it could be converted to Peg:

word = (apostrophe?  letter alpha*) / ","

Finally, several Peg implementations allow for the use of regular expressions directly in their grammar. See how your third rule could be represented in such Peg:

letter = [a-zA-Z]

Deppending on the language you are using and the specific Peg implementation, a few things may change, but I hope these guidelines point you to the right direction.

Upvotes: 4

Related Questions