{"id":3958,"date":"2024-02-26T13:44:33","date_gmt":"2024-02-26T12:44:33","guid":{"rendered":"https:\/\/oopm.org\/?page_id=3958"},"modified":"2024-11-29T13:58:11","modified_gmt":"2024-11-29T12:58:11","slug":"10-1-2-an-expression-parser","status":"publish","type":"page","link":"https:\/\/oopm.org\/?page_id=3958","title":{"rendered":"10.1.2 An expression parser"},"content":{"rendered":"
\"image_pdf\"<\/a>\"image_print\"<\/a><\/div>\n

In this section, we show how to write a parser for our simple expression grammar. The parser reads a string of characters and checks whether or not the string is a valid expression as described by the grammar.<\/p>\n\n\n\n

We assume that the input string to the parser is in the String inn<\/code>. We define a method nextChar<\/code> that assigns the next character in inn<\/code> to the variable ch<\/code>, but skipping all blank characters. The variable pos<\/code> keeps track of the current position in inn<\/code>. When the end of inn<\/code> is reached, the null-character is assigned to ch<\/code>.<\/p>\n\n\n\n

inn: ref<\/strong> String\npos: var<\/strong> integer\nch: var<\/strong> integer    \nnextChar:\n   -- read the next character from inn and assign it to ch\n   -- skip white space like blanks and end-of-lines\n   -- return ch = 0, if at the end of inn\n   pos := pos + 1\n   if (pos <= inn.length) :then\n      ch :=  inn.get[pos]\n      if (ch = ' ') :then\t\n         restart(nextChar)\t\n    else\n      ch := 0<\/code><\/pre>\n\n\n\n
The parser is based on a technique of so-called recursive<\/em> methods – we return to recursion later.<\/p>\n\n\n\n
For each nonterminal symbol of the grammar we define a method that checks if the input is in accordance with the nonterminal.<\/p>\n\n\n\n
For the nonterminal <Exp><\/code> , we define the method exp<\/code>:<\/p>\n\n\n\n
   exp:\n      -- parse an expression generated from <Exp>\n      term\n      if (ch = '+') :then\n         nextChar\n         restart(exp)<\/code><\/pre>\n\n\n\n
The exp<\/code>-method starts by calling the term<\/code>-method, which we assume parses an expression as generated by <Term><\/code>. <\/p>\n\n\n\n
If the next character is a '+'<\/code>, nextChar<\/code> is called to assign the next char into ch<\/code> and then execution of exp<\/code> Is restarted. <\/p>\n\n\n\n
Given that term<\/code> actually parses a string described by <Term><\/code>, exp<\/code> will parse an sequence:<\/p>\n\n\n\n
<term> + <term> + ... + <term><\/code><\/pre>\n\n\n\n
We may now show the term<\/code>-method, which is similar to exp<\/code>:<\/p>\n\n\n\n
term:\n    primary\n    if (ch = '*') :then\n        nextChar\n        restart(term)<\/code><\/pre>\n\n\n\n
The term<\/code>-method assumes that the method primary<\/code> parses a string described by <Primary><\/code> and will then parse a sequence:<\/p>\n\n\n\n
<Primary> * <Primary> * ... * <Primary><\/code><\/pre>\n\n\n\n
Next we look at the <Primary> <\/code>rule, which has  the form:<\/p>\n\n\n\n
<Primary> ::= \"(\" <Exp> \")\" | <Number><\/code><\/pre>\n\n\n\n
This give us the following primary<\/code>-method:<\/p>\n\n\n\n
primary:\n   -- parse an expression generated from <Primary>\n   if (ch = '(') :then\n      nextChar        \n      exp\n      if (ch = ')') :then\n         nextChar\n      :else\n         syntaxError(1)\n   :else\n        number<\/code><\/pre>\n\n\n\n
If the next character (ch<\/code>) is a left-bracket (\"(\"<\/code>), it calls nextChar<\/code> and then exp<\/code>. When exp<\/code> returns, the next character must be a right-bracket (\")\"<\/code>), otherwise we have an error in the string – and a syntax error is reported.<\/p>\n\n\n\n
If the next character is not a left-bracket, the number<\/code>-method is called and again we assume that number<\/code> parses a string as described by <Number><\/code>.<\/p>\n\n\n\n
The call of the exp<\/code>-method is an example of a recursive call. We return to recursion in the section below.<\/p>\n\n\n\n
Next we show the number<\/code>-method and the digit<\/code>-method:<\/p>\n\n\n\n
number:\n   -- parse an expression generated from <Number>\n   digit\n   moreDigits: do<\/strong>\n      if (ascii.isDigit(ch)) :then\n         digit\n         restart(moreDigits)\ndigit:\n   -- parse an expression generated from <Digit>\n   if (ascii.isDigit(ch)) :then\n      nextChar\n   :else\n      syntaxError(3)<\/code><\/pre>\n\n\n\n
The number<\/code>-method expects at least one digit, which is reflected in the digit<\/code>-method that repoerts a syntax error if ch<\/code> is not a digit. <\/p>\n\n\n\n
Finally we may show how to start parsing:<\/p>\n\n\n\n
parse:\n   -- parse the expression assigned to inn below\n   inn :=  \"10 + 11 * (1 + 9)\"\n   console.print(\"Parse: \" + inn + \"\\n\")\n   nextChar\n   exp      \n   if (ch <> ascii.null) :then\n          syntaxError(3)<\/code><\/pre>\n\n\n\n
The parse<\/code>-method calls exp<\/code> and when exp<\/code> returns, ch<\/code> must be the ascii.null<\/code> character.<\/p>\n\n\n\n
Recursion<\/h2>\n\n\n\n
Recursion is a technique for defining an entity in terms of a simpler version of itself. In order for this to work, there must be a terminating condition that can be defined without applying recursion, i.e. a recursive definition must be to a part of the entity that is simpler than the original entity.<\/p>\n\n\n\n
The expression grammar is and example of a recursive definition. A nonterminal like <Exp><\/code> is defined using <Exp><\/code> on the rigt side of the rule, the same is the case for <Term><\/code>. The rule for <Primary><\/code> is an example of an indirect recursion, since <Primary><\/code> is defined by means of <Exp><\/code> which in turn is defined by means of <Primary><\/code>.<\/p>\n\n\n\n
The terminating conditions here is that an <Exp><\/code> can be a <Term><\/code>, a <Term><\/code> can be a <Primary><\/code>, which can be a <Number><\/code>.<\/p>\n\n\n\n
The methods of the parser are example recursive methods and they follow the same scheme as the grammar except that only the indirect recursion of exp<\/code> via primary<\/code> is explicitly encoded.<\/p>\n\n\n\n
The snapshot below shows the situation of the the invocation of parse of the string \"11 * (1 + 9) + 12\"<\/code> at the point where the substring \"11 * (\" <\/code>has been parsed and primary<\/code> has made a recursive invocation of exp<\/code> which has invoked term<\/code>. The red arrow (--><\/mark><\/code>) shows the point of execution in exp<\/code> and the black arrow (--><\/code>) shows the point of invocation of exp<\/code> in primary<\/code>.<\/p>\n\n\n\n
\n
\n
  primary:\n     -- parse an expression generated from <Primary>\n     if (ch = '(') :then\n        nextChar        \n-->     exp\n        if (ch = ')') :then\n           nextChar\n        :else\n           syntaxError(1)\n     :else\n        number\n  exp:\n     -- parse an expression generated from <Exp>\n--><\/mark> term\n    if (ch = '+') :then\n       nextChar\n       restart(exp)<\/code><\/pre>\n<\/div>\n\n\n\n
\n
\"\"<\/figure>\n<\/div>\n<\/div>\n\n\n\n
<\/p>\n
\n\t\t<\/a>\n\t\t<\/div>","protected":false},"excerpt":{"rendered":"
In this section, we show how to write a parser for our simple expression grammar. The parser reads a string of characters and checks whether or not the string is a valid expression as described by the grammar. We assume that the input string to the parser is in the String inn. We define a […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":1282,"menu_order":2,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-3958","page","type-page","status-publish","hentry"],"mb":[],"mfb_rest_fields":["title","gutenberg_elementor_mode"],"_links":{"self":[{"href":"https:\/\/oopm.org\/index.php?rest_route=\/wp\/v2\/pages\/3958","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/oopm.org\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/oopm.org\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/oopm.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/oopm.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=3958"}],"version-history":[{"count":36,"href":"https:\/\/oopm.org\/index.php?rest_route=\/wp\/v2\/pages\/3958\/revisions"}],"predecessor-version":[{"id":9981,"href":"https:\/\/oopm.org\/index.php?rest_route=\/wp\/v2\/pages\/3958\/revisions\/9981"}],"up":[{"embeddable":true,"href":"https:\/\/oopm.org\/index.php?rest_route=\/wp\/v2\/pages\/1282"}],"wp:attachment":[{"href":"https:\/\/oopm.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=3958"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}