{"id":640,"date":"2009-05-20T07:34:09","date_gmt":"2009-05-20T06:34:09","guid":{"rendered":"http:\/\/fiber-space.de\/wordpress\/?p=640"},"modified":"2009-05-20T14:04:26","modified_gmt":"2009-05-20T13:04:26","slug":"vhdl-grammars-and-the-parser-sandwich","status":"publish","type":"post","link":"http:\/\/fiber-space.de\/wordpress\/2009\/05\/20\/vhdl-grammars-and-the-parser-sandwich\/","title":{"rendered":"VHDL grammars and the parser sandwich"},"content":{"rendered":"<p>Eli Bendersky has <a href=\"http:\/\/eli.thegreenplace.net\/2009\/05\/19\/parsing-vhdl-is-very-hard\/\">mentioned<\/a> some problems of parsing VHDL. I was quite pleased though finding the Postlexer idea being discussed in the following <a href=\"http:\/\/ftp.informatik.rwth-aachen.de\/Publications\/CEUR-WS\/Vol-255\/paper11.pdf\">paper<\/a> which provides a more thorough treatment of VHDL parsing issues.<\/p>\n<p>They call it &#8220;Auxiliary Terminal Generator&#8221; which is a more precise notation of what I call a &#8220;Postlexer&#8221;. In that case a Postlexer resolves ambiguities caused by context sensitivity. The solution is to introduce auxiliary terminal symbols in between two context free passes &#8211; the one for lexical analysis and parsing.<\/p>\n<p>What I distaste about their approach is that they coupled the grammar with the Postlexer using parsing actions.<br \/>\nApparently generations of computing scientists enjoyed squeezing as much information as possible into their grammars instead of acknowledging the obvious: a separate parsing phase is often required for non-trivial grammars and since the problems are specific one can leave it entirely to a powerful general purpose language and the programmer to solve them. As a consequence the parser isn&#8217;t portable across languages but at least the grammars are.<\/p>\n<p>Generally speaking one has to consider three functions now instead of two:<\/p>\n<p><strong>The Parser Sandwich<\/strong><\/p>\n<pre lang=\"python\">Lexer: Parsetable String -&gt; Tokenstream\r\nPostlexer: Tokenstream -&gt; Tokenstream\r\nParser: Parsetable Tokenstream -&gt; Tree<\/pre>\n<p>`Lexer` and `Parser` shall be universally applicable for any language whereas the `Postlexer` is always specific and can be omitted if the whole language can be described in a context free way.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Eli Bendersky has mentioned some problems of parsing VHDL. I was quite pleased though finding the Postlexer idea being discussed in the following paper which provides a more thorough treatment of VHDL parsing issues. They call it &#8220;Auxiliary Terminal Generator&#8221; &hellip; <a href=\"http:\/\/fiber-space.de\/wordpress\/2009\/05\/20\/vhdl-grammars-and-the-parser-sandwich\/\">Continue reading <span class=\"meta-nav\">&rarr;<\/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],"tags":[],"_links":{"self":[{"href":"http:\/\/fiber-space.de\/wordpress\/wp-json\/wp\/v2\/posts\/640"}],"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=640"}],"version-history":[{"count":7,"href":"http:\/\/fiber-space.de\/wordpress\/wp-json\/wp\/v2\/posts\/640\/revisions"}],"predecessor-version":[{"id":647,"href":"http:\/\/fiber-space.de\/wordpress\/wp-json\/wp\/v2\/posts\/640\/revisions\/647"}],"wp:attachment":[{"href":"http:\/\/fiber-space.de\/wordpress\/wp-json\/wp\/v2\/media?parent=640"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/fiber-space.de\/wordpress\/wp-json\/wp\/v2\/categories?post=640"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/fiber-space.de\/wordpress\/wp-json\/wp\/v2\/tags?post=640"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}