Brute Force Parser – Regular or Context Free Grammar
Definition
How
to Run Brute Force Parser on Regular or CFG
JFLAP defines a context free grammar G = (V, T, S, P), where
V is a set of variables (S represents the start
variable).
T is a set of terminals.
P is a set of productions.
Productions are in the form A->x, where A is a single variable
and x is a string of zero or more terminals and variables.
Since JFLAP accepts context-free grammars (CFG), it automatically works with regular grammars (thus, right-linear grammar) as they are also context-free grammars. In a right-linear grammar all productions must have at most one variable in the right-hand side and this variable must be to the right of all the terminals.
We will begin by loading the grammar that we entered in the previous tutorial. You can either enter the grammar (shown in Enter Grammar tutorial) or load the file contextfreeGrammar.jff. Then you can click on Input, followed by Brute Force Parse.
After clicking 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 “aabbbbbccc” (a2b5c3) in the input text field. Then either click Start or press Enter key.
Brute Force Parser notifies you that the string you entered is accepted. Now, we can click on the Step button to see how we can derive that string using our productions. After clicking the Step button twice, your window should look like this.
Notice that at the bottom of the window there is a message, “Derived bBc from B”. This message tells us about the last production that was applied. We can also view the Derivation Table to see how the string is derived by the grammar.
To change to Derivation Table mode, click on Noninverted Tree and select Derivation Table. The Brute Force Parse window should change to :
The derivation table shows the productions that are applied (shown under Production) and the result of applying those productions to the start variable (shown under Derivation). It gives a clear picture of how Brute Force Parsing is working. After clicking Step until we reach our input string, the Brute Force Parse is finished and the Derivation Table and Noninverted Tree should look like these :
This concludes our brief tutorial on Brute Force Parser – Regular or CFG. Thanks for reading!