{"id":2395,"date":"2011-10-03T20:55:00","date_gmt":"2011-10-03T19:55:00","guid":{"rendered":"http:\/\/touk.pl\/blog\/?guid=4485904760c911598e7ad6e0bb71519e"},"modified":"2023-03-22T12:00:46","modified_gmt":"2023-03-22T11:00:46","slug":"grammar-parser-in-c","status":"publish","type":"post","link":"https:\/\/touk.pl\/blog\/2011\/10\/03\/grammar-parser-in-c\/","title":{"rendered":"Grammar parser in C++"},"content":{"rendered":"<p>Recently I stumbled upon implementing a simple parser in C++. The task is very classic, however, I couldn\u2019t find any good resources on the web to help me out.<br \/>\nI tried different tools (including ANTLR), but finally, the easiest way I found was bison + flex. It\u2019s unbelievable that this technology from 1989 is still actively developed. The latest stable release is from May 14, 2011. Moreover, many essential projects make use of it. Among them are Ruby, PHP, Google Go, and Bash shell.<br \/>\nSo I decided to create a minimalistic example that works from scratch.<br \/>\nI published the code on GitHub <a href=\"http:\/\/github.com\/rafalrusin\/calculator\">Calculator<\/a>, so you can check it out.<br \/>\nThe whole example is 88 lines long and evaluates common expressions, like 2+2*2-13*(7+19\/2).<br \/>\nLet\u2019s start with lexer. In flex, you need to define regular expressions, which produce tokens. Such tokens are later processed by a scanner. So we have to define calculator.lex, like this:<br \/>\nFlex will generate yylex() function, which we can call later to produce tokens. Next, we need to create a scanner (calculator.y), which specifies a grammar. It\u2019s simple like that:<br \/>\nHere, we specify types for all tokens using C\/C++ union like structure. Variable $$ is used to store result of particular reductions.<br \/>\nAdditionally, we need to specify %left precedence for +, -, *, \/ operators to resolve shift \/ reduce conflicts between them.<br \/>\nAnd that\u2019s basically it. We have a working expression parser.<br \/>\nI implemented it so that executable takes a file name containing expressions as an argument.<br \/>\nSo you can try .\/calculator input.txt to see the result.<\/p>\n","protected":false},"excerpt":{"rendered":"Recently I stumbled upon implementing a simple parser in C++. The task is very classic, however, I couldn\u2019t&hellip;\n","protected":false},"author":35,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[11],"tags":[693],"class_list":["post-2395","post","type-post","status-publish","format-standard","category-development-design","tag-c"],"_links":{"self":[{"href":"https:\/\/touk.pl\/blog\/wp-json\/wp\/v2\/posts\/2395","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/touk.pl\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/touk.pl\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/touk.pl\/blog\/wp-json\/wp\/v2\/users\/35"}],"replies":[{"embeddable":true,"href":"https:\/\/touk.pl\/blog\/wp-json\/wp\/v2\/comments?post=2395"}],"version-history":[{"count":10,"href":"https:\/\/touk.pl\/blog\/wp-json\/wp\/v2\/posts\/2395\/revisions"}],"predecessor-version":[{"id":15460,"href":"https:\/\/touk.pl\/blog\/wp-json\/wp\/v2\/posts\/2395\/revisions\/15460"}],"wp:attachment":[{"href":"https:\/\/touk.pl\/blog\/wp-json\/wp\/v2\/media?parent=2395"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/touk.pl\/blog\/wp-json\/wp\/v2\/categories?post=2395"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/touk.pl\/blog\/wp-json\/wp\/v2\/tags?post=2395"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}