expression_grammar | ![]() |
![]() |
![]() |
![]() |
We've dealt with the parts of the parser that make YAC a programmable calculator. Time now to return to the grammar that parses the right hand side of these statements. The grammar governing these expressions is rather complex. Nonetheless, many of the rules are of the same form
rule1 ::= rule2 (operator_list rule2)*
and the semantic actions applied after such a statement is parsed successfully are also similar in form. If this were "normal" code, we'd try and factor things into a function and invoke it multiple times, once for each grammar snippet.
Of course, this isn't "normal" code. For one thing, Spirit's rule's cannot be copied, so returning the resulting expression from a function is not possible. Nonetheless, Spirit does indeed possess the tool for the job. It's called the functor_parser. Before revealing this jewel, however, let's consider the rules at the hard end, number and function. After all, it's these that we end up operating on.
Parsing a number, a variable or a function call all result in the creation of a new node on the computational stack. For example:
number
= real_p
[
push_back(number.stk, new_<const_value_node>(arg1))
]
| self.local_vars
[
push_back(number.stk,
new_<variable_node>(address_of(arg1)))
]
| self.global_vars
[
push_back(number.stk,
new_<variable_node>(address_of(arg1)))
]
;
a number or a variable found in one of the variable symbol tables causes a node to be pushed onto the stack closure variable attached to the number rule. Note that the variable_node constructor takes a pointer to the data stored in the symbol table. address_of is a lazy function that that effectively wraps &arg1.
Thereafter, the stack closure attached to number is pushed up the cascade of rules that govern the grammar in its entirety, eventually reaching the top where it is assigned to the closure that is 'returned' from the expression_grammar itself:
top = expr[self.stk = arg1];
// a whole heap of intervening rules whose form
// is similar to that of mult_expr.
mult_expr
= expr_atom[ mult_expr.stk = arg1 ]
>> '*'
>> expr_atom[ mult_expr.stk += arg1,
push_back(mult_expr.stk,
/* function node pointing to "mult#2" */)
]
;
expr_atom
= number
[
expr_atom.stk = arg1
]
| func
[
expr_atom.stk = arg1
]
| ...
;
On each step back up the stack, the stack attached to each rule is created from the contributions 'returned' from the rules below. What could be easier?
Turn now to the func rule that is used to parse a function call. Parsing a function call such as foo(1+2,bar(3,4)) is a little more complicated than just recognizing a variable x. After all, it is the symbol tables of previously declared variables that do all the work for us there. Here, we must first generate the mangled name that is used to identify a function in the symbol table of known functions. This mangling requires the raw function name, here "foo", and the function arity, here 2, to generate the mangled name. Once again, closures attached to the func rule make it easy to assemble the constituent parts:
func
= name
[
func.arity = 0,
func.name = construct_<std::string>(arg1, arg2)
]
>> ('(' >> !list_p(arg, ',') >> ')')
;
arg
= expr
[
func.arity += 1,
func.stk += arg1
]
;
where name is a name_grammar variable and expr is the topmost rule governing an expression. (Any such expression is valid in the function argument list.) Having accumulated all this data, we're now in a position to ascertain whether the function is known:
func
= ...
>> ('(' >> !list_p(arg, ',') >> ')')
[
func.func_ptr
= checked_find_(var(self.functions),
mangled_name(func.name, func.arity))
]
checked_find_ returning a shared_ptr copy of the appropriate entry in the symbol table. If the function is not found, checked_find_ returns an empty shared_ptr.
Finally, we use Spirit's if_p(condition)[then-parser].else_p[else-parser] utility to either add a node to the computational stack or cause the parser to fail:
...
>> if_p(func.func_ptr != function_ptr_t())
[
epsilon_p
[
push_back(func.stk,
new_<sys_function_node>(func.func_ptr))
]
]
.else_p[nothing_p]
;
Note that this block doesn't actually consume any more input data.
![]() |
![]() |
![]() |
Copyright © 2004 Angus Leeming
Distributed under the Boost Software License,
Version 1.0. (See accompanying file
LICENSE_1_0.txt or copy at
http://www.boost.org/LICENSE_1_0.txt
)