-
Notifications
You must be signed in to change notification settings - Fork 2
AFParser Examples
This example illustrates how to create a C++11 AFParser object that counts the occurrences of the letter ‘a’. The example makes use of the FlexTokenizer class to scan input entered by the user, which is assumed to only contain a's. The AFG makes use of flow variables and semantic actions to determine the number of a’s parsed.
This example makes use of two AFParser objects, IT_NUM and REC_NUM, to accept the language of all binary numbers. The example also uses a custom lexical analyzer BinaryTokenizer to tokenize each bit in the binary number. The use of semantic actions calculates the decimal value of the accepted binary number and stores the result into flow variable z.
This example is an expression interpreter that prompts the user for a simple mathematical expression that can contain the four basic arithmetic operations (+, -, *, and /) and may contain parenthesis. The example, uses the FlexTokenizer class to employ a Flex specification that allows the interpreter to accept integers, doubles, and numbers expressed in scientific notation. This example illustrates the use of flow variables to extract the semantic value of the terminal num and calculate the result of the expression. The FlexTokenizer class is employed to scan from stdin.
Let us modify the previous example to use more flow variables. More specifically, we’ll use adjust the previous example’s AFG to require inherited attributes, or in this case in-flow variables. The example employs a parser that parses the following grammar:
<E> ::= <T> <TT> { TT.st := T.val; E.val := TT.val }
<TT1> ::= + <T> <TT2> { TT2.st := TT1.st + T.val; TT1.val := TT2.val }
<TT1> ::= - <T> <TT2> { TT2.st := TT1.st - T.val; TT1.val := TT2.val }
<TT> ::= ε { TT.val := TT.st }
<T> ::= <F> <FT> { FT.st := F.val; T.val := FT.val }
<FT1> ::= * <F> <FT2> { FT2.st := FT1.st * F.val; FT1.val := FT2.val }
<FT1> ::= / <F> <FT2> { FT2.st := FT1.st / F.val; FT1.val := FT2.val }
<FT> ::= ε { FT.val := FT.st }
<F1> ::= - <F2> { F1.val := -F2.val }
<F> ::= { <E> ) { F.val := E.val }
<F> ::= unsigned_int{ F.val := unsigned_int.val }
Where st is an inherited attribute and val is a synthesized attribute. The Flex specification is the same as the previous example's. Notice the use of flow variables in the AFG implement some of the above semantic rules, like TT.st := T.val and TT.val := TT.st, automatically.
This example builds upon the original calculator example by allowing the use of exponents, logarithms, and the basic trigonometric functions sin, cos, and tan. This example also makes use of a symbol table to store symbols and their corresponding values for reference in mathematical expressions. As such, the Flex specification was altered to tokenize identifiers for the symbol table and keywords associated with the newly supported math functions. Further, the AFG has been altered to adjust for the new features.
This example exemplifies the ability to use flow variables that are not of a primitive type, in this case complex numbers. The example employs the FlexTokenizer class to tokenize input. To enable flow variables to be complex numbers, a ComplexNum class was created. The example overrides the insertion operator of the TokenStream class to extract and store the semantic value of a given token, representing a complex number, in an out-flow variable properly.
The ComplexNum class overrides the arithmetic operators and they are used on ComplexNum flow variables in the semantic actions of the AFG. The result is a clean looking AFG that isn’t cluttered with complicated semantic actions.
Definite clause grammars are a way of expressing a grammar in a logic programming language such as Prolog. Though DCGs can be used for formal and natural languages, it is primarily used to parse natural languages due to its ability to represent linguistic features fairly concisely. Consider the following set of DCG rules:
sentence --> pronoun(subject), verb_phrase.
verb_phrase --> verb, pronoun(object).
pronoun(subject) --> [he].
pronoun(subject) --> [she].
pronoun(object) --> [him].
pronoun(object) --> [her].
verb --> [likes].
The AFG employed in this example accept a language of simple present-tense pronoun sentences with a small subset of verbs. The verbs accepted are: like(s), love(s), hate(s). Present-tense pronouns include: She, He, I, We, me, us, etc. Overall, the AFG accepts sentences such as "He likes her" and "I hate him" but not sentences such as "I hate I".
The following example exhibits an AFParser object that uses AFG involving the * operation (0 or more repetitions), ~ operation (optional), and the + operation (1 or more repetitions). The grammar has two nonterminals that are assigned the names “INPUT” and “MORE” using the name() member function from the ParserPrinter class. Using the ParserPrinter class, we print the productions of both nonterminals and print the ParseTree object created when parsing the input string “aaacdcdcd” to stdout.