{"id":557,"date":"2008-08-15T16:00:50","date_gmt":"2008-08-15T23:00:50","guid":{"rendered":"https:\/\/www.reenigne.org\/blog\/?p=557"},"modified":"2008-06-06T20:28:56","modified_gmt":"2008-06-07T03:28:56","slug":"parsing-expression-grammar-grammar","status":"publish","type":"post","link":"https:\/\/www.reenigne.org\/blog\/parsing-expression-grammar-grammar\/","title":{"rendered":"Parsing expression grammar grammar"},"content":{"rendered":"

I have found that a fun thing to do is make up grammars for computer languages – figure out what syntax rules work well and what is ambiguous (to both humans and computers – it seems the two are more closely related in this respect that I would initially have imagined).<\/p>\n

The language I eventually want to write<\/a> will have a parser generator (probably generating packrat parsers from Parsing Expression Grammars) built in, so I thought I would write a grammar for the grammars accepted by that – a rather self-referential exercise. I keep going back and forth on some of the syntax details, but this is how it looks at the moment:<\/p>\n

\r\n\/\/ Characters\r\n\r\nCharacter = `\\n` | `\\r` | ` `..`~`;\r\n\r\nEndOfLine = `\\r\\n` | `\\n\\r` | `\\n` | `\\r`\r\n\r\nAlphabeticCharacter = `a`..`z` | `A`..`Z` | `_`;\r\n\r\nAlphanumericCharacter = AlphabeticCharacter | `0`..`9`;\r\n\r\nEscapedCharacter = `\\\\` (`\\\\` | `\\`` | `n` | `r` | `\"`);\r\n\r\n\r\n\/\/ Space\r\n\r\nMultilineComment :=\r\n  `\/*` (\r\n      MultilineComment\r\n    | !`*\/` Character\r\n  )* \"*\/\"\r\n\/\/ Note that this is recursive because multi-line comments nest!\r\n\/\/ To match C-style (non-nesting comments), use \r\n\/\/ CStyleMultilineComment := `\/*` (!`*\/` Character)* \"*\/\";\r\n\r\nSpace =\r\n  (\r\n      ` `\r\n    | EndOfLine\r\n    | `\/\/` (!EndOfLine Character)*\r\n    | MultilineComment\r\n  )*;\r\n\r\n_ := !AlphanumericCharacter [Space];\r\n\r\n\r\n\/\/ Tokens\r\n\r\nIdentifier := AlphabeticCharacter AlphanumericCharacter*;\r\n\r\nCharacterLiteral := `\\`` ( Character-(`\\n` | `\\\\` | `\\``) | EscapedCharacter )* \"`\";\r\n  \/\/ No spaces matched afterwards\r\n\r\nStringLiteral := `\"` ( Character-(`\\n` | `\\\\` | `\"`) | EscapedCharacter )* \"\\\"\";\r\n  \/\/ Optionally matches _ afterwards\r\n\r\n\/\/ Productions and rules\r\n\r\nCharacterRange := CharacterLiteral \"..\" CharacterLiteral\r\n\r\nRule :=\r\n  (\r\n    (\r\n      (\r\n          Identifier\r\n        | \"[\" Rule \"]\"\r\n        | \"!\" Rule\r\n        | \"&\" Rule\r\n        | \"(\" Rule \")\"\r\n        | \"EndOfFile\"\r\n        | StringLiteral\r\n        | CharacterRange\r\n        | CharacterLiteral\r\n      ) \/ \"|\" \/ \"-\" \/ \"\\\\\" \/ \"\/\"\r\n    ) [\"+\" | \"*\"]\r\n  )*;\r\n\r\nProduction := [Identifier] (\":=\" | \"=\") Rule \";\";\r\n\r\n= [_] Production* EndOfFile;\r\n<\/pre>\n
The rules are as follows:<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n
Rule1 | Rule2<\/td>\nprioritized alternative<\/td>\n<\/tr>\n
Rule1 Rule2<\/td>\nsequence<\/td>\n<\/tr>\n
Rule*<\/td>\nKleene star<\/td>\n<\/tr>\n
Rule+<\/td>\nRule Rule*<\/td>\n<\/tr>\n
!Rule<\/td>\ndoes not match Rule<\/td>\n<\/tr>\n
&Rule<\/td>\nmatches Rule but is not consumed<\/td>\n<\/tr>\n
(Rule)<\/td>\norder of operations<\/td>\n<\/tr>\n
Rule1-Rule2<\/td>\nmatches Rule1 but not Rule2<\/td>\n<\/tr>\n
Rule1\/Rule2<\/td>\na sequence of strings matching Rule1 separated by strings matching Rule2 – left-associative (i.e. X := Y\/Z  =>  X := Y (Z Y)*)<\/td>\n<\/tr>\n
Rule1\\Rule2<\/td>\na sequence of strings matching Rule1 separated by strings matching Rule2 – right-associative (i.e. X := Y\\Z  =>  X := Y [Z X])<\/td>\n<\/tr>\n
Char1..Char2<\/td>\nmatches a character between the character in Char1 and the character in Char2<\/td>\n<\/tr>\n<\/table>\n
Having a single grammar for both Parser and Lexer is nice in some respects but does introduce some additional complications. Some strings (those I’ve called CharacterLiterals here) must match exactly (no whitespace is consumed after them) and some (those I’ve called StringLiterals here) must consume any whitespace that appears after them (done by optionally matching the _ production). Similarly with productions – those created with “:=” optionally match _ at the end.<\/p>\n
The root production has no name.<\/p>\n
The “\/” and “\\” delimiters makes it really easy to write grammars for expressions with infix operators. For example, the core of the C++ expression production is:<\/p>\n
\r\nLogicalOrExpression := CastExpression\r\n  \/ (\".*\" | \"->*\")\r\n  \/ (\"*\" | \"\/\" | \"%\")\r\n  \/ (\"+\" | \"-\")\r\n  \/ (\"<<\" | \">>\")\r\n  \/ (\"<\" | \">\" | \"<=\" | \">=\")\r\n  \/ (\"==\" | \"!=\")\r\n  \/ \"&\"\r\n  \/ \"^\"\r\n  \/ \"|\"\r\n  \/ \"&&\"\r\n  \/ \"||\";\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
I have found that a fun thing to do is make up grammars for computer languages – figure out what syntax rules work well and what is ambiguous (to both humans and computers – it seems the two are more closely related in this respect that I would initially have imagined). The language I eventually […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[27],"tags":[],"class_list":["post-557","post","type-post","status-publish","format-standard","hentry","category-language"],"_links":{"self":[{"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/posts\/557","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/comments?post=557"}],"version-history":[{"count":0,"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/posts\/557\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/media?parent=557"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/categories?post=557"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.reenigne.org\/blog\/wp-json\/wp\/v2\/tags?post=557"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}