CS 381 Homework 3 – Syntax

CS 381 Homework 3 – Syntax
Submit a pdf for problems 1 – 4 and a Haskell *.hs file for problem 5.
1. Using the grammar below, show a parse tree and a leftmost derivation for the sentence
A = B * (C+A)
. <assign>  <id> = <expr>
 <expr>  <expr> * <term>
 | <term>
 <term>  <factor> + <term> | <factor> - <term>
 | <factor>
 <factor>  ( <expr> )
 | <id>
<id>  A | B | C
2. Rewrite the following BNF to add the prefix ++ and -- unary operators of Java.
. <assign>  <id> = <expr>
 <expr>  <expr> * <term>
 | <term>
 <term>  <factor> + <term> | <factor> - <term>
 | <factor>
 <factor>  ( <expr> )
 | <id>
<id>  A | B | C
3. Show that the following grammar is ambiguous
. <compare>  <boolexpr> == <boolexpr>
<boolexpr>  <boolexpr> AND <boolexpr>
 | <boolexpr> OR <boolexpr>
| <bool>
| NOT <bool>
<bool>  <boolvalue> | <boolvar>
<boolvalue>  True | False | 0 | 1
<boolvar> → u | v | w
i
CS 381 Homework 3 – Syntax
Submit a pdf for problems 1 – 4 and a Haskell *.hs file for problem 5.
4. Write a grammar G for the language L consisiting of strings of 0’s and 1’s that are the binary
representation of odd integers greater that 4. For example 11 L, 101L, 110 L. Draw parse
trees for the strings 1011 and 1101
5. Below is the EBNF grammar for the animal sentence language
<sentence> -> <noun> <verb> [<noun>]
 | <sentence> `and` <sentence>

 <noun> -> <adj> <noun> | <noun> `and` <noun>
 | `cats` | `dogs` | `ducks` | `bunnies`
 <verb> -> `chase` | `cuddle` | `hug` | `scare`
 <adj> -> `silly` | `small` | `old` | `happy`
Note: the nonterminals are in < > and the terminals are in ` `.
Using the animal.hs template provided.
a) Define the abstract syntax for the animal language as a Haskell data type.
b) Provide “pretty printing“ functions for the sentences in the language.
c) Provide functions to build a sentence.
d) Write a function isNice to determine if a sentence only contains the verbs hug and
cuddle.
e) Write a function to build a sentence that is a conjunction of other sentences.
f) Write a function wordCount that computes the number of words in a sentence
Parse tree assigns
if
I Exers
A
Cefr term
terms Factors
stators chxpr
aidsI cterm B
factor
t terms t
I factor
Cid
a
Lid
C
1A
Lefmost derivation
assign aid ex pro
A c ex Pr
A exp r terms
A term factor
A factor expry
A factor a term
A c id factor term
A B aid I factors
A B c aids
A B Ct A
added the prefix and unary ope rears
assign id L Expts
expr expr term I term
term factor term factors terms
Kfactors
factor 7 exprs
I aid l c id kids
id A IB IC
I add prefix tt and in the front of aids Because
ascoding to the given grammar cid is terminals which
means cid are variables according to Java we can
add't t and befora a varible
0
Let me generate two parse trees for the
sentence Y OR V V AND W
parse tree
compare
bootexpy Cboolexpts
bootexPD OR boolexpu cboolexth AND TootexPV
blots blot abbot abbot
I
I l I bool var
Ibootvars aboot0981 boolvav
U V V W
Pause tree 20
compare
bootexpy boolexpts
I
Cboolexth AND bootexpu bonexpp 012 cb ol abbot abbot I 1 I boot
aboot0981
boolvav bool var I V V W i boolvar
U
The first parse the represents the sentenie
U OR U V AND W and the second
parse tree represents sentenie
V AND W A OR V Therefor The
grammer is ambiguous Because the same
i put sentence could be parsed in two
different ways
Let G u 0.1 P S f
where S is
the start symbol K sit is set variabe 0,1 is set
setofterminals and P is the see of production
rules defined as i
s 1A
A oh
A 1
This grammar generates binary representation
of odd integers greater than 4 where the first
character is always 1 followed by zero or more
1 s and o's alternating ending with a 0
parse tree for the strong loll I pause tree for the stray 1101
S S
1 It A
8h I
It o s