yagg::Tutorial - Tutorial for yagg
# To use the generator ./yagg -m nonterminals.yg terminals.lg ./output/progs/generate 5
This tutorial will show you how to use yagg, by way of two examples. In the first example, we create a simple logical expression generator from scratch. In the second example, we create a more sophisticated logical expression generator from existing parser/lexer input files, such as those used by YACC/Bison and LEX/FLEX. These examples, plus another more sophisticated fault tree generator are included with the distribution in the examples/ directory.
It is assumed that the reader knows a little about formal grammars. Ideally, the reader would have some experience writing grammars for input to parser generators like YACC and Bison.
Let's say that we want to create a logical expression generator that generates expressions containing binary operators, parentheses, negation, and atomic propositions. Examples might be -(p or q), p => -q, and p and (q or r).
Here is a simple grammar that would create such expressions:
wfe : wfe binary_operator wfe | "(" wfe ")" | unary_operator wfe | atomic ; binary_operator : "<=>" | "and" | "or" | "=>" ; unary_operator : "-" ; atomic : "p" | "q" | "r" ;
You can place the above grammar verbatim into a "language grammar" input file, adding a line containing %% at the top of the file. This is enough for the generator to do its job. Running the generator as:
%%
$ yagg -r2 foo.yg
will generate the generator, compile it, and run it to create expressions of length 2.
Another way to write the input files is to put the productions for terminals such as "(" and atomic into a "terminal generator" file. This approach is more similar to the approach taken by tools such as Lex and YACC, which separate the lexical analysis of tokens from the grammar-based parsing. Here's the resulting grammar file
"("
atomic
Here's the grammar file, logical_expression.yg:
%% wfe : wfe BINARY_OPERATOR wfe | LEFT_PAREN wfe RIGHT_PAREN | UNARY_OPERATOR wfe | ATOMIC ;
Here we're using upper-case as a convention to indicate the terminals. Notice that the strings associated with BINARY_OPERATOR, UNARY_OPERATOR, and ATOMIC have been removed. They are located in the terminal grammar file, logical_expression.lg:
BINARY_OPERATOR
UNARY_OPERATOR
ATOMIC
%% ( "<=>" | "and" | "or" | "=>" ) return BINARY_OPERATOR; "-" return UNARY_OPERATOR; "(" return LEFT_PAREN; ")" return RIGHT_PAREN; ( "p" | "q" | "r" ) return ATOMIC;
This file is similar to a LEX input file, but instead of regular expressions you must provide one of several terminal formats. (We'll describe these shortly.) For example, the last rules says that an atomic proposition is either p, q, or r.
Next, use these input files to generate the generator:
$ yagg -m logical_expression.yg logical_expression.lg
And then run the generator:
$ ./output/progs/generator 3
You can use the -r flag to run the generator for a given length. You can also use the -o flag to place the output in a different directory. -o can specify a directory on a remote machine using any of the rsync formats. In this case, -m and -r will execute on the remote machine instead of the local one.
You'll notice that the generator prints out a number of very similar expressions, such as p and q versus q and p. You can control how terminals are generated by using one of several terminal specification formats:
"p"
A simple string is used wherever the terminal appears.
( "p" | "q" )
When such a terminal appears, multiple versions will be generated, one for each alternative.
[ "p" | "q" ]
Terminals of this type are treated as belonging to an equivalence class. That is, a "q" is only generated if the current string already has a "p". This is useful for terminals that represent things like variable names.
It's easier to explain equivalence with an example. Suppose you use the simple alternation: "p" | "q" for a terminal ATOMIC. The output for ATOMIC ATOMIC will be:
"p" | "q"
ATOMIC ATOMIC
p p p q q p q q
In this case, the first and last generated string are basically the same because they both have identical elements. Similarly, the second and third generated string are the same since they both have different elements. As far as our logical expressions example, we only really care about the first two cases. We can use the equivalence alternation form to get what we want: [ "p" | "q" ]. In this case, the output will be:
p p p q
[ "p#" ]
This form is the same as the equivalence alternation, except that the names are generated as they are needed by substituting "#" in the string with a number starting at 1, and the number of generated strings is unbounded. For example, if you use [ "p#" ] for ATOMIC, the output for ATOMIC ATOMIC will be:
#
p1 p1 p1 p2
If we want to remove the generation of strings with semantically redundant atomic propositions, we would need to modify the ATOMIC terminal specification like so:
[ "p" | "q" | "r" ] return ATOMIC;
If you now rerun the yagg and string generator:
$ yagg -r 3 logical_expression.yg logical_expression.lg
you will see that the strings have been constrained. Also note that the generation is faster this time---the comilation process only needs to recompile the implementation of the ATOMIC generator component.
This example is in the examples/logical_expression_simple/ directory of the distribution. See the README file.
README
In this second example, let's say that you've already created a parser for your format using LEX and YACC, or FLEX and Bison. If you have, you probably already have the following:
A lex.l input file for LEX/FLEX
A yacc.y input file for YACC/Bison
An include file for headers needed by the parser and lexer
Extra files for custom data types and whatnot needed for parsing
The following instructions tell you how to convert them into input files for yagg. In this example, I will use the example parser located in the examples/logical_expression_constrained/logical_expression_parser/ directory of the distribution. (The .y and .l files are in the src/logical_expression_parser subdirectory.) The resulting files are in the examples/logical_expression_constrained directory, along with a README file.
(By the way, if you have problems or have to alter the steps while working with your own files, please let me know so that I can update this tutorial.)
Copy lex.l to lex.lg
Delete everything in the definitions section, except for an %{ ... %} and %option prefix=..., if they are there.
%{ ... %}
%option prefix=...
In the rules section:
Delete everything in the action blocks except any return TOKEN statements
return TOKEN
Delete any start conditions from the rules
Delete any rules with empty action blocks
Replace any regular expressions in the rules with appropriate generators. (See above.)
In the code header block, comment out the #include for the parser-generated header file. (This would normally by y.tab.h, but you may have renamed it.)
If you used the -Pfoo flag to change the symbol prefix from yy, you'll need to add an %option prefix=foo.
%option prefix=foo
Copy yacc.y to yacc.yg
For any rule that has a side-effect, add another "unaction" block immediately following that reverses the effect. You don't need to worry about any changes to $$---they will be handled automatically. If you have an undo block, and if any of the positional parameters such as $1 are pointers, you only need to delete them if (1) they would normally be deleted in the action block, and (2) if you actually use them in the unaction block.
$$
$1
If you compare the .yg file to the original .y file, you'll see that I added only one undo block, because all the other action blocks only manipulated $$.
Any functions that you call should not have side effects. If they do, you'll need to reverse them in the unaction block(s).
Create a directory like input_user_code_myproject/src/model.
Put all your source code in that directory, being careful to create proper subdirectories if you need them. For example, if you have #include "module/header.h", you'd want to put header.h in input_user_code_myproject/src/model/module. (You don't however, need to change the include to #include at all. The default C++ extension is .cc--you may need to rename your files. (Alternatively, you can copy the GNUmakefile and edit the value of CCFILEEXT.)
#include "module/header.h"
#include
Run the following command to create the C++ generator code.
./yagg -f -u input_user_code_myproject yacc.yg lex.lg
By default, the output is placed in the output/ directory. Change to that directory and run GNU make to compile it.
cd output make
You can do this automatically by giving yagg the -m flag
Generate the strings by running the generate program in the progs/ directory, giving it a positive integer for the length of the strings to generate.
./progs/generate 9
Specify any length for the generated strings you want. An error message will be displayed if you choose too small a number.
This example is in the examples/logical_expression_constrained/ directory of the distribution. See the README file.
The most common problem you will encounter is exponential explosion of strings. If yagg produces strings that you think it should not, first check that the grammar actually says what you think it says.
For example, consider this grammar, which generates strings of "a" and "b" in any order (see ab.yg in examples/ab):
node_list : node_list node | node ; node : "a" | "b" ;
Obviously we could move node to the terminal file and use equivalence classes to limit the generated strings. But for now, let's assume explore ways to limit the strings using the grammar only.
node
One way is to force all "a"'s to precede all "b"'s. We can do this by modifying the grammar (see ab_grammar_constrained.yg in examples/ab):
node_list : a_list b_list | a_list | b_list ; a_list : a_list "a" | "a" ; b_list : b_list "b" | "b" ;
to change an unordered list of "a"'s and "b"'s so that "b"'s will follow "a"'s.
Another approach might be to keep the same grammar but add context-sensitive checks (see ab_check_constrained.yg in examples/ab). In order to do this, we need to pass the names of the nodes back up the grammar productions, which means that we need to define some return types and add action blocks:
// Include some declarations that we need %{ #include <list> #include <string> using namespace std; %} // Define the return types %union { list<string> text_list; string text; } // Define the grammar production return types %type <text_list> node_list %type <text> node %% node_list : node_list node { if ($$.size() > 0 && $$.back() == "b" && $2 == "a") yyerror("\"a\" can't follow \"b\"!"); else { $$.push_back($2); } } | node { $$.push_back($1); }; node : "a" { $$ = $1; } | "b" { $$ = $1; } ;
In this case, we check the node_list as we build it to make sure that we never add an "a" after a "b". The call to yyerror is how the generator knows that the string is invalid. Note that I didn't need to write any unaction blocks because the actions did not change any state other than $$.
yyerror
Which method is better? I would use the latter only for constraints which truly are context sensitive. Restructuring the grammar also results in faster string generation because there is no time wasted generating strings that will only be invalidated later.
NOTE: this grammar takes advantage of a feature of the generator--that the %union isn't really used as a union, so you can define types of different (and dynamic) sizes. Bad things would happen if you tried to use this grammar with YACC or Bison. To fix it, you would need to change the %union types to pointers and add new and delete to the action blocks, and change "a" and "b" to tokens.
%union
new
delete
See ab_check_constrained_pointers.yg in examples/ab for these changes. You can also compare this to the ab_parser.y file for the parser in the ab_parser subdirectory.
For a more realistic example of limiting the generated strings, compare the fault_trees and fault_trees_constrained examples in the examples directory of the distribution.
To control output, first create a user_code/src/progs/ directory. Run yagg once so that it creates the output/ directory. Copy output/src/progs/generate.cc to user_code/src/progs/. Modify the Print_Strings function, which inserts a space by default between strings and adds a newline at the end.
Print_Strings
Now, when you run yagg, add the -u user_code option so that your modified generate.cc will override the normal generated one. If you want more control, you can remove the whitespace insertion in Print_Strings, then make whitespace an explicit part of your grammar.
David Coppit <david@coppit.org>
To install yagg, copy and paste the appropriate command in to your terminal.
cpanm
cpanm yagg
CPAN shell
perl -MCPAN -e shell install yagg
For more information on module installation, please visit the detailed CPAN module installation guide.