Need to Design C programs to transform propositional logic
well formed formulae (wffs), i.e. syntactically correct formulae, into wffs in conjunctive
normal form (CNF). Such representation is used by automatic theorem provers.
1.2 Grammar
You are asked to write a compiler that processes tasks specifed by a grammar. To make
things concrete consider the following table:
input filtered output
P
{
a<=>b^c=>d|~p;? ? ? ? ? TASK-P>Error
~p||q&c;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? TASK-P>Error
2&1|p;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? TASK-P>Error
((p&q)=>c;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? TASK-P>Error
(p&q)=>c;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? TASK-P>Success
}
The left-hand side is a possible input to your compiler. The letter P on the first line indicates that the task is the parsing of formulae. Then a list of formulae is given between curly brackets, each formula being terminated by a semicolon. The input file does not need to be arranged in rows as shown in the table. (Everything could have been included on a single line.) However, you are asked to generate an output file which produces the exact display shown on the right-hand side column after filtering by the grep command. (Before filtering your output ¯le may contain other messages.)
?
## Deliverables
The tasks to perform are defined by the following grammar:
task ----> taskid `{' w²ist `}'
? ? ? ? ? ? ? ? ? ? ? ? ? ? ;
taskid ---> `C' LEVEL
? ? ? ? ? ? ? ? ? ? ? | KEY
? ? ? ? ? ? ? ? ? ? ? ;
wffist ---> wff wffist
? ? ? ? ? ? ? ? ? ? ? |wff
? ? ? ? ? ? ? ? ? ? ? ;
? ? ? wff etc
Here i have just described the higher structure of the language. You are not asked to produce your own parse tree for this higher structure. You should use this structure to create actions to process each wff sequentially. For each wff a parse tree will have to be
created to perform the task required. When a wff is syntactically correct (no parsing error) the tree should be destroyed (i.e memory freed) before processing the next wff in the list. (You are not asked to recover the memory allocated to tree nodes in case of syntax error in the formula.)
The possible task identi¯ers (taskid) are
P Parse wff
R display Reverse Polish notation
E display Expression from tree
C 1 to C 7 convert formula to CNF, 7 levels of transformation
So in the above grammar, LEVEL is an integer taking values between 1 included and 7
included while KEY is one of the letters P, R, E.
The tasks are described in detail in the next sections
The rest of the grammar is as follows
wff ---> expr `;'
? ? ? ? ? ? ? |`;'
? ? ? ? ? ? ? ;
expr ---> CONSTANT
? ? ? ? ? ? ? | VARIABLE
? ? ? ? ? ? ? | expr EQUIVALENT expr
? ? ? ? ? ? ? | expr IMPLY expr
? ? ? ? ? ? ? | expr OR expr
? ? ? ? ? ? ? | expr AND expr
? ? ? ? ? ? ? | NOT expr
? ? ? ? ? ? ? | `(' expr `)'
? ? ? ? ? ? ? ;
This grammar is ambiguous. To specify an unambiguous grammar you have to add
associativity and operator priority rules.
token? ? ? ? ? ? ? ? ? ? ? ? string? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? mathematical
CONSTANT? ? ? ? [01] (0 for F) and (1 for T)? ? ? ? ? ? ? ? F, T
VARIABLE? ? ? ? ? ? ? ? any lower case letter [a-z]? ? ? ? ? ? a, b, .etc
EQUIVALENT? ? ? ? <=>
IMPLY? ? ? ? ? ? ? ? ? ? ? ? =>
OR? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? |
AND? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? &
NOT? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ~
Table 1: Token representation
The unary NOT is non-associative. IMPLY is right-associative. All other binary
operators are left-associative. Note that in this case the left-associative operators are
also fully associative. What does this mean? The associativity of operators in a computer
language indicates the order in which operations are performed. For example p & q & r
is executed from left to right. From an execution point of view this is equivalent to
(p & q) & r. Both expressions produce the same parse tree. The full (mathematical)
associativity indicates that the order operations may be performed can be changed.
For example (p & q) & r and p & (q & r) are algebraically equivalent (they give the
same results for all choices of values for p, q, r) but their parse trees are di®erent. The
property of mathematical associativity will be used in one of the tasks.
The precedence of the operators is as follows:
priority(NOT) > priority(AND) > priority(OR) >
> priority(IMPLY) > priority(EQUIVALENT)
Table 1 indicates strings that should be used to represent the tokens. In addition, as the
character `;' is used as end of formulae you will allow the input to contain space, tab
(`\t'), and newline (`\n') characters.
Rather than using associativity and precedence features of yacc you may want to use
multi-level expression grammars by adapting the example you were given in lectures for
arithmetic expressions.
An example of w® is given in the next section.
Important note: You should realize that the overall grammar is problematic because
the domain for LEVEL is [1-7] and the domain for CONSTANT is [01]. Hence 1 belongs
to both domains. So you should alter the grammar to enable processing by lex and yacc.
You may do that in various ways, either rede¯ning rules and tokens to avoid domain
overlapping or using a common token in place of CONSTANT and LEVEL with range
checking in actions associated with grammatical rules. If you should choose the latter
approach then you would need to use the function yyerror, and the instruction YYERROR.
+----[=>]---+
|? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? |
|? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? |
[~]? ? ? ? ? +---[<=>]----+
|? ? ? ? ? ? ? ? ? |? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? |
|? ? ? ? ? ? ? ? ? |? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? |
(a)? ? ? ? ? (b)? ? ? ? ? ? ? ? ? ? ? ? ? +--[|]---+
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? |? ? ? ? ? ? ? ? ? ? ? ? ? ? |
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? |? ? ? ? ? ? ? ? ? ? ? ? ? ? |
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? +-[&]-+? ? ? ? ? ? ? ? ? (1)
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? |? ? ? ? ? ? ? |
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? |? ? ? ? ? ? ? ? |
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (c)? ? ? ? ? ? ? (b)
Figure 1: Graphical representation of parse tree for ~a=>(b<=>c&b|1)
1.3 CNF
Any wff can be transformed into a CNF. A CNF is a conjunction of disjunctive clauses,
defined as follows:
² A literal is a variable, a constant or the negation of a variable or a constant
² A disjunctive clause is a disjunction of literals, e.g: a | b | ~c | ~1 (Note that
a clause may contain a single literal.)
² A CNF is a conjunction of disjunctive clauses, e.g: (a | b | ~c) & ~b & ~e
CNF that contain constants can be simpli¯ed.
Deliverables
1-? ? ? ? lex program
2-? ? ? ? yacc program
3-? ? ? ? tree.c
4-? ? ? ? make file