Brute Force Parser – Unrestricted Grammar
Definition
How
to Run Brute Force Parser on Unrestricted Grammar
An unrestricted grammar is similar to a context-free grammar (CFG), except that the left side of a production may contain any nonempty string of terminals and variables, rather than just a single variable.
In a CFG, the single variable on the left side of a production could be expanded in a derivation step. In an unrestricted grammar, multiple variables and/or terminals that match the left-side of a production can be expanded by the right-side of that production.
We will begin by loading an unrestricted grammar for the language anbncn, n>0. Load the file unrestrictedGrammar.jff. After loading the file your grammar editor should look like this :
After clicking Input, then Brute Force Parse, you should see a window similar to this.
Now you can input a string and check whether it is accepted. Enter the string “aabbcc” (a2b2c2) in the input text field. Then either click Start or press Enter key.
For the first 3 Steps, Brute Force Parser runs just like it did with context-free grammar. However, after clicking the Step button the fourth time, you will notice that Brute Force Parser combines variable “B” and terminal “b” in a blue oval and replaces them with the two nodes b and B using the “Bb->bB” production. Your window should look similar to this one :
After clicking the Step button several times, it becomes clearer that Brute Force Parser is combining two adjacent variables or terminals (representing the left-side of productions) and replacing them with the right-side of their production. Finally, when you reach the last step, you will see that the input string is accepted. Here is the Non-inverted Tree and Derivation Table of the final result. Note in the tree that the leaf nodes from left to right result in the string “aabbcc” we derived.
This concludes our brief tutorial on Brute Force Parser – Unrestricted Grammar. Thanks for reading!