Homework 3 – Syntax


Rate this product

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
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
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
I Exers
Cefr term
terms Factors
stators chxpr
aidsI cterm B
t terms t
I factor
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
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
Let me generate two parse trees for the
sentence Y OR V V AND W
parse tree
bootexpy Cboolexpts
bootexPD OR boolexpu cboolexth AND TootexPV
blots blot abbot abbot
I l I bool var
Ibootvars aboot0981 boolvav
Pause tree 20
bootexpy boolexpts
Cboolexth AND bootexpu bonexpp 012 cb ol abbot abbot I 1 I boot
boolvav bool var I V V W i boolvar
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
1 It A
8h I
It o s

Scroll to Top