{"id":2045,"date":"2012-05-20T17:01:39","date_gmt":"2012-05-20T16:01:39","guid":{"rendered":"http:\/\/fiber-space.de\/wordpress\/?p=2045"},"modified":"2022-10-12T12:30:45","modified_gmt":"2022-10-12T11:30:45","slug":"greedy-grammars-and-any","status":"publish","type":"post","link":"http:\/\/fiber-space.de\/wordpress\/2012\/05\/20\/greedy-grammars-and-any\/","title":{"rendered":"Greedy grammars and Any"},"content":{"rendered":"

I only vaguely remember my first encounter with a parser generator which must by dated back to the late 1990s. I guess it was Spark<\/a> by John Aycock, an Early parser. What puzzled me back then was the need to be explicit down to the character level.\u00a0 Regular expression engines, albeit cryptic, were a revelation because one could specify the structural information one needed and match the rest using a ‘.’ which is the wildcard pattern that matches any<\/em> character.<\/em><\/p>\n

I came back to Any<\/em> in the Trail parser generator lately. I was motivated by writing a reversible C preprocessor. Unlike conventional C preprocessors which are used in the compilation chain of C code, a reversible C preprocessor can used to refactor C code, while retaining the preprocessor directives and the macro calls. This is basically done by storing the #define directive along with the code to be substituted and the substitution. The substituted code and the substitution are exchanged after the refactoring step, such that it looks like no substitution happened at all.<\/p>\n

A comprehensive C preprocessor grammar can be found on the following<\/a> MSDN site. What is most interesting to us are the following two EBNF productions:
\n#define identifier<\/em>[(<\/strong> identifier<\/em>opt<\/sub>, <\/strong>…<\/em> ,<\/strong> identifier<\/em>opt<\/sub> )<\/strong>] token-string<\/em>opt<\/sub><\/p>\n

\n
token-string <\/em>: <\/dt>\n
String of tokens <\/p>\n<\/dd>\n<\/dl>\n<\/blockquote>\n

The String of tokens<\/em> phrase this is Any+<\/em>.<\/p>\n

Bon app\u00e9tit<\/h3>\n

Suppose one defines two macros<\/p>\n

#define min(a,b) ((a)<(b)?(a):(b))\r\n\r\n#define max(a,b) ((a)<(b)?(b):(a))<\/pre>\n
Obviously the defining string of the `min` macro can be recognized using token-string<\/em> but how can we prevent that token-string<\/em> eats the `max` macro as well? Once in motion token-string has a sound appetite and will eat the rest. The solution to this problem in case of regular expressions is to make Any<\/em> non-greedy. The non-greediness can easily be expressed using the following requirement:<\/p>\n
If `S | Any` is a pattern with `S!=Any`. If S can match a character, `S` will be preferred over `Any`.<\/p>\n
In the production rule<\/p>\n
R: ... Any* S ...<\/pre>\n
we can be sure that if S matches in R then Any won't be used to match - although it would match if we leave it greedy. Same goes with<\/p>\n
R: ... (Any* | S) ...<\/pre>\n
Non greediness in grammars<\/h3>\n
Grammars are more complicated than regular expressions and we have to take more care about our greediness rules. To illustrate some of the problems we take a look on an example<\/p>\n
R: A B | C\r\nA: a Any*\r\nB: b\r\nC: c<\/pre>\n
`Any` causes a follow\/first conflict between A and B. Making `Any` non-greedy alone won't help because a grammar rule or its corresponding NFA is always greedy! It follows a longest match policy and an NFA will be traversed as long as possible. So once the NFA of A is entered it won't be left because of the trailing `Any*`.<\/p>\n
Detecting the trailing `Any` in A is easy though. We solve the follow\/first conflict with a trailing `Any` by embedding `A` into `R`. Embedding strategies are the centerpiece of Trail and they shall not be recapitulated here. Just so much: embedding A in R doesn't destroy any information relevant for parsing. If A has been embedded `Any*` will be delimited by `B` to the right and we can safely apply R without the danger of `Any` consuming a token 'b'.<\/p>\n
Eventually we have to re-apply our embedding strategy: if `A` is a rule with a trailing `Any` and `A` is embedded in `B` and `B` has a trailing `Any` after<\/em> this embedding\u00a0 then `B` will be embedded wherever possible.<\/p>\n
A short experiment<\/h3>\n
Here is a mini-Python grammar is used to detect Python class definitions.<\/p>\n
file_input: (NEWLINE | stmt)* ENDMARKER\r\nclassdef: 'class' NAME ['(' Any+ ')'] ':' suite\r\nsuite: simple_stmt | NEWLINE INDENT stmt+ DEDENT\r\nsimple_stmt: Any* NEWLINE\r\nstmt: simple_stmt | compound_stmt\r\ncompound_stmt: classdef | Any* suite<\/pre>\n
 <\/em><\/p>\n
Unlike a real Python grammar it is fairly easy to build. All rules are taken from the Python 2.7 grammar but only `file_input`, `suite` and `stmt` remained unchanged. In all other cases we have replaced terminal\/non-terminal information that isn't needed by `Any`.<\/p>\n
 <\/p>\n

\n<\/em><\/p>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
I only vaguely remember my first encounter with a parser generator which must by dated back to the late 1990s. I guess it was Spark by John Aycock, an Early parser. What puzzled me back then was the need to … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[12,23,4],"tags":[],"_links":{"self":[{"href":"http:\/\/fiber-space.de\/wordpress\/wp-json\/wp\/v2\/posts\/2045"}],"collection":[{"href":"http:\/\/fiber-space.de\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/fiber-space.de\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/fiber-space.de\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/fiber-space.de\/wordpress\/wp-json\/wp\/v2\/comments?post=2045"}],"version-history":[{"count":36,"href":"http:\/\/fiber-space.de\/wordpress\/wp-json\/wp\/v2\/posts\/2045\/revisions"}],"predecessor-version":[{"id":2321,"href":"http:\/\/fiber-space.de\/wordpress\/wp-json\/wp\/v2\/posts\/2045\/revisions\/2321"}],"wp:attachment":[{"href":"http:\/\/fiber-space.de\/wordpress\/wp-json\/wp\/v2\/media?parent=2045"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/fiber-space.de\/wordpress\/wp-json\/wp\/v2\/categories?post=2045"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/fiber-space.de\/wordpress\/wp-json\/wp\/v2\/tags?post=2045"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}