{"id":3691,"date":"2024-02-20T12:22:24","date_gmt":"2024-02-20T11:22:24","guid":{"rendered":"https:\/\/oopm.org\/?page_id=3691"},"modified":"2025-01-14T12:36:09","modified_gmt":"2025-01-14T11:36:09","slug":"10-1-1-complete-grammar-example","status":"publish","type":"page","link":"https:\/\/oopm.org\/?page_id=3691","title":{"rendered":"10.1.1 A simple expression grammar"},"content":{"rendered":"
\"image_pdf\"<\/a>\"image_print\"<\/a><\/div>\n

In this section, we extend the grammar example with code to represent a complete grammar, a parser, and an evaluator. The reader may skip this section and the subsequent ones on the expression parser and the abstract syntax tree during the first reading of this book.<\/p>\n\n\n\n

We use a grammar for describing aritemhetic expressions of digits using '+',<\/code> '*'<\/code> and parentheses:<\/p>\n\n\n\n

Start: <Exp>\n<Exp> ::= <Exp> \"+\" <Term> | <Term>\n<Term> ::= <Term> \"*\" <Primary> | <Primary>\n<Primary> ::= <Number> | \"(\" <Exp> \")\"\n<Number> ::= <Number> <Digit> | <Digit>\n<Digit> ::= \"0\" | \"1\" | \"2\" | \"3\" | \"4\" | \"5\" | \"6\" | \"7\" | \"8\" | \"9\" <\/code><\/pre>\n\n\n\n
The start symbol of the grammar is the nonterminal <Exp><\/code>.<\/p>\n\n\n\n
The nonterminal symbols are: <Exp><\/code>, <Term><\/code>, <Primary><\/code>, <Number><\/code>, and <Digit><\/code>.<\/p>\n\n\n\n
The terminal symbols are: \"+\"<\/code>, \"*\"<\/code>, \"(\"<\/code>, \")\"<\/code> and the digits \"0\"<\/code> – \"9\"<\/code>.<\/p>\n\n\n\n
We declare an ExpressionGrammar<\/code> as a sub of Grammar<\/code>:<\/p>\n\n\n\n
ExpressionGrammar: obj<\/strong> Grammar\n   -- declaration of symbols\n   -- declaration of rules\n   -- specification of start symbol<\/code><\/pre>\n\n\n\n
The symbols are declared as follows:<\/p>\n\n\n\n
   expSy: obj<\/strong> Nonterminal(\"Exp\")\n   termSy: obj<\/strong> Nonterminal(\"Term\")\n   primarySy: obj<\/strong> Nonterminal(\"Primary\")\n   numberSy: obj<\/strong> Nonterminal(\"Number\")\n   digitSy: obj<\/strong> Nonterminal(\"Digit\")\n   add: obj<\/strong> Terminal(\"+\")\n   mult: obj<\/strong> Terminal(\"*\")\n   leftB: obj<\/strong> Terminal(\"(\")\n   rightB: obj<\/strong> Terminal(\")\")<\/code><\/pre>\n\n\n\n
To generate the rules, we introduce a method for each nonterminal. The one for <Exp><\/code> looks as follows:<\/p>\n\n\n\n
   mkExpRule: addRule(expSy)\n      S: ref<\/strong> SymbolList\n      S := SymbolList.insertList((ExpSy,add,termSy))\n      R.alternatives.insert(Alternative(S))\n      S := SymbolList.insertList(termSy)\n      alt := Alternative(S)\n      R.alternatives.insert(alt)<\/code><\/pre>\n\n\n\n
As can bee seen, mkExpRule<\/code> is a submethod of the method addRule<\/code>, which we have added to class Grammar<\/code>. In addition, we have added class SymbolList<\/code> with a print<\/code> method:<\/p>\n\n\n\n
class<\/strong> Grammar:\n   ...\n   class<\/strong> SymbolList: OrderedList(#Symbol)\n       print:\n          scan\n             current.print\n   addRule(L: ref<\/strong> Nonterminal): \n      R: ref<\/strong> Rule\n      R := Rule\n      R.leftSide := L\n      inner(addRule)\n      rules.insert(R) <\/code><\/pre>\n\n\n\n
The method addRule<\/code> has the leftside of the rule to be added as a parameter L<\/code>. It generates a Rule<\/code>-object and assign its reference to R<\/code>, and then assigns L<\/code> to the leftSide<\/code> of R<\/code>. Then it executes inner(addRule)<\/code> implying that the mainpart of mkExpRule<\/code> is executed. When returning from inner, the Rule<\/code> R<\/code> is inserted into the list of rules.<\/p>\n\n\n\n
The expression SymbolList.insertList((ExpSy,add,termSy))<\/code> may need an explanation:<\/p>\n\n\n\n
    \n
  1. First SymboList<\/code> is evaluated creating a SymbolList<\/code>-object returning a reference to this newly created object.<\/li>\n\n\n\n
  2. Then insertList((ExpSy,add,termSy))<\/code> is invoked on the reference to the new SymbolList<\/code>-object.<\/li>\n\n\n\n
  3. The parameter of insertList<\/code> is an array and the argument of the invocation is the array-literal <\/mark>(ExpSy,add,termSy)<\/code> – array-literal is introduced in section