Annulleret

C program with Compiler(repost)

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

Evner: C programmering, Ingeniørarbejde, Linux, MySQL, PHP, Software Arkitektur, Software Testning, UNIX

Se mere: what need for an operator, what is syntax in programming, what is r programming, what is computer programming used for, what is computer program, what is binary tree in c, what is binary tree, what is binary notation, what is a variable in programming, what is a variable in computer programming, what is a string in programming, what is a function in computer programming, what does mean in c programming, what does mean in computer programming, what does design mean, what does binary, what are binary trees, use case levels, tree structure representation, tree structure programming

Om arbejdsgiveren:
( 1 bedømmelse ) United Kingdom

Projekt ID: #3811018

5 freelancere byder i gennemsnit $741 på dette job

spx2vw

See private message.

$85 USD in 8 dage
(39 bedømmelser)
4.7
ifline

See private message.

$3060 USD in 8 dage
(3 bedømmelser)
3.7
jgjugy

See private message.

$51 USD in 8 dage
(1 bedømmelse)
1.4
manigaultvw

See private message.

$212.5 USD in 8 dage
(0 bedømmelser)
0.0
gauravavw

See private message.

$297.5 USD in 8 dage
(0 bedømmelser)
0.0