Boolean Grammar

Linklist

Who Will Have These Attr?

First to know, all symbol that has a .truelist or .falselist attributes must be a boolean-like element.

• E -> a > b will have .truelist and .falselist
• E -> true will only have .truelist

What Stored Inside Linklist?

To be simple, it’s a list of TAC index. We already said an element has such attribute must be a boolean-like element, then it would eventually be evaluated into true or false at some point during the program running process, then:

• .truelist: When program reach any index contained in E.truelist, it could promise E is evaluated to true.
• .falselist: Similar to .truelist but promise E is evaluated to false.

For example, if we know in a Parse Tree Node E has .truelist=[2,5] and .falselist=[3], then we essentially know:

• If program reach 2nd or 5th line of TAC, then at that point, the boolean element that E represent must be true.
• If program reach 3rd line of TAC, then the boolean element of E represent must be false.

Boolean Grammar Design

Note that when dealing with E -> E1 and M E2 and E -> E1 or M E2, the non-terminal M is actually redundant in the level of Context Free Grammar.

However, we still need it if we want to achieve short circuit effect, we need to perform backpatching for E1.truelist or E1.falselist (determined by op) just at the same time when M is getting processed in the tree. Checkout the image below:

Conditional Control

• .nextlist When reach these index, program need to skip to some next part. (The node in some of the upper part is responsible to pass up and finally backpatching these “skip request”)
• .breaklist Similar to .nextlist, used by break; symbol exclusively.

Checkout TSU PDFP231 for more detailed info.

Conclusion

In this paradigm, we focus on passing up two categories of data: Control and BackpatchMark.

Control: Control data means all kind of “linklists”, they are spawned in some leaves nodes and keep passing up until reach some symbol that has the ability to backpatch them.

BackpatchMark: These M symbols are redundant to CFG, but useful to use as a mark of a place we may need to jump to. Those symbols that has the ability to backpatch the linklist usually get their patch point info from these M symbols’ .gotostm attribute.