http:^^www.cs.washington.edu^education^courses^322^96w^hw4soln^hw4soln.html
来自「This data set contains WWW-pages collect」· HTML 代码 · 共 217 行
HTML
217 行
Date: Wed, 08 Jan 1997 20:43:18 GMTServer: NCSA/1.4.2Content-type: text/html<!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN"><!Converted with LaTeX2HTML 95 (Thu Jan 19 1995) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds ><HEAD><TITLE>CSE 322 Assignment 4 Solution Set Monday, January 29, 1996</TITLE></HEAD><BODY><meta name="description" value="CSE 322 Assignment 4 Solution Set Monday, January 29, 1996"><meta name="keywords" value="hw4soln"><meta name="resource-type" value="document"><meta name="distribution" value="global"><P> <BR> <HR><A NAME=tex2html1 HREF="node1.html"><IMG ALIGN=BOTTOM ALT="next" SRC="http://www.cs.washington.edu/general/latex2html_icons//next_motif.gif"></A> <IMG ALIGN=BOTTOM ALT="up" SRC="http://www.cs.washington.edu/general/latex2html_icons//up_motif_gr.gif"> <IMG ALIGN=BOTTOM ALT="previous" SRC="http://www.cs.washington.edu/general/latex2html_icons//previous_motif_gr.gif"> <BR><B> Next:</B> <A NAME=tex2html2 HREF="node1.html"> About this document </A><BR> <HR> <P><P><H1>CSE 322 Assignment 4 Solution Set Monday, January 29, 1996</H1><P><STRONG></STRONG><P><P><STRONG></STRONG><P><P><OL><LI> Number 36 on page 69. Better yet construct the derivation tree for<IMG ALIGN=MIDDLE ALT="" SRC="img1.gif">.<P>For the derivations, I'll use the following abbreviations:<P><b><</b>E<b>></b> means <b><</b>expression<b>></b><BR> <b><</b>SE<b>></b> means <b><</b>simple expression<b>></b><BR> <b><</b>T<b>></b> means <b><</b>term<b>></b><BR> <b><</b>F<b>></b> means <b><</b>factor<b>></b><BR> <b><</b>AO<b>></b> means <b><</b>adding operator<b>></b><BR> <b><</b>MO<b>></b> means <b><</b>multiplying operator<b>></b><BR> <b><</b>V<b>></b> means <b><</b>variable<b>></b><BR> <b><</b>EV<b>></b> means <b><</b>entire variable<b>></b><BR> <b><</b>VI<b>></b> means <b><</b>variable identifier<b>></b><BR> <b><</b>I<b>></b> means <b><</b>identifier<b>></b><BR> <b><</b>IT<b>></b> means <b><</b>identifier tail<b>></b><BR> <b><</b>L<b>></b> means <b><</b>letter<b>></b><BR> <b><</b>UC<b>></b> means <b><</b>unsigned constant<b>></b><BR> <b><</b>UN<b>></b> means <b><</b>unsigned number<b>></b><BR> <b><</b>UI<b>></b> means <b><</b>unsigned integer<b>></b><BR> <b><</b>D<b>></b> means <b><</b>digit<b>></b><BR> <b><</b>DS<b>></b> means <b><</b>digits<b>></b><BR><P>Also, I'm using the following CFG productions in place of their BNF equivalents:<P><b><</b>unsigned integer<b>></b> <IMG ALIGN=BOTTOM ALT="" SRC="img2.gif"> <b><</b>digit<b>></b> <b>|</b> <b><</b>digit<b>></b> <b><</b>digits<b>></b> <BR> <b><</b>digits<b>></b> <IMG ALIGN=BOTTOM ALT="" SRC="img3.gif"> <b><</b>digit<b>></b> <b><</b>digits<b>></b> <b>|</b> <IMG ALIGN=BOTTOM ALT="" SRC="img4.gif"> <BR> <b><</b>identifier<b>></b> <IMG ALIGN=BOTTOM ALT="" SRC="img5.gif"> <b><</b>letter<b>></b> <b><</b>identifier tail<b>></b> <BR> <b><</b>identifier tail<b>></b> <IMG ALIGN=BOTTOM ALT="" SRC="img6.gif"> <b><</b>letter or digit<b>></b> <b><</b>identifier tail<b>></b> <b>|</b> <IMG ALIGN=BOTTOM ALT="" SRC="img7.gif"> <BR><P><P><IMG ALIGN=BOTTOM ALT="" SRC="img8.gif"><P><P><LI><P><OL><LI> The given grammar is unambiguous because there are two leftmostderivations for the string <b>ababab</b>:<P><IMG ALIGN=BOTTOM ALT="" SRC="img9.gif"><P><P><IMG ALIGN=BOTTOM ALT="" SRC="img10.gif"><P>There are two derivation trees for <b>ababab</b>, as well:<P><IMG ALIGN=MIDDLE ALT="" SRC="img11.gif">-0.75<IMG ALIGN=MIDDLE ALT="" SRC="img12.gif"><IMG ALIGN=MIDDLE ALT="" SRC="img13.gif">-0.75<IMG ALIGN=MIDDLE ALT="" SRC="img14.gif"><P><LI> The ambiguity in the grammar is due to the <IMG ALIGN=BOTTOM ALT="" SRC="img15.gif">production. The grammar allows multiple derivation trees of any terminal string thatcan be derived from <IMG ALIGN=BOTTOM ALT="" SRC="img16.gif">.The following grammar corrects this problem:<P><IMG ALIGN=BOTTOM ALT="" SRC="img17.gif"><P>Intuitively, what this does is force immediate parsing on the leftside of the string, by forcing the parse to the <b>A</b> productions. A formal argumentfor why this grammar is ambiguous might comefrom the following observation: if we consider any string made up of balanced parenthesis, it can be described uniquely asa set of nested parenthesis surrounding some empty or non-empty stringof balanced parenthesis, concatenated with some empty ornon-empty string of balanced parenthesis. This description corresponds exactly to the grammar: the <b>A</b> productions generate the ``nested'' part and the <b>S</b> productions generate the ``concatenated'' part.</OL><P><LI> Use the construction given in class for producing a regular grammarfrom a regular expression to construct a regular grammar which generatesthe language defined by the regular expression <IMG ALIGN=MIDDLE ALT="" SRC="img18.gif">.<P>Since we eventually need to generate a unique set of non-terminals for each <b>a</b> and <b>b</b> in the regular expression, we annotate the expressionwith indices: <IMG ALIGN=MIDDLE ALT="" SRC="img19.gif">. These indices aren'tintended to mean anything, but we'll use them for bookeeping as we develop the grammar. For each set of productions, we denote any starting symbol<b>S</b> as <IMG ALIGN=BOTTOM ALT="" SRC="img20.gif">. If any nonterminal and its productions can be eliminated because it is unreachable from the starting symbol, it is marked with <IMG ALIGN=MIDDLE ALT="" SRC="img21.gif">.<P><IMG ALIGN=BOTTOM ALT="" SRC="img22.gif"><IMG ALIGN=BOTTOM ALT="" SRC="img23.gif"><P><IMG ALIGN=BOTTOM ALT="" SRC="img24.gif"><IMG ALIGN=BOTTOM ALT="" SRC="img25.gif"><P><IMG ALIGN=BOTTOM ALT="" SRC="img26.gif"><IMG ALIGN=BOTTOM ALT="" SRC="img27.gif"><P><IMG ALIGN=BOTTOM ALT="" SRC="img28.gif"><IMG ALIGN=BOTTOM ALT="" SRC="img29.gif"><P><IMG ALIGN=BOTTOM ALT="" SRC="img30.gif"><IMG ALIGN=BOTTOM ALT="" SRC="img31.gif"><P>One grammar for the language described by <IMG ALIGN=MIDDLE ALT="" SRC="img32.gif"> is then<P><IMG ALIGN=BOTTOM ALT="" SRC="img33.gif"><P>where <b>P</b> is given by the productions below:<P><IMG ALIGN=BOTTOM ALT="" SRC="img34.gif"><P><LI> Suppose <IMG ALIGN=MIDDLE ALT="" SRC="img35.gif"> where <IMG ALIGN=BOTTOM ALT="" SRC="img36.gif"> in the given grammar.Properties i) and ii) can be shown to hold for any such <b>x</b> by (strong) induction on the length of the leftmost derivation of <b>x</b>.<P><b>Basis:</b> (n=1) Suppose <IMG ALIGN=MIDDLE ALT="" SRC="img37.gif"> and <IMG ALIGN=BOTTOM ALT="" SRC="img38.gif">. Thereis only one such terminal string <b>x</b>, namely <b>x=ab</b>. <UL><LI> (property i) <IMG ALIGN=BOTTOM ALT="" SRC="img39.gif">,<b>a</b>, and <b>ab</b> are the only prefixes of <b>ab</b>. For all of these prefixes, the number of <b>a</b>'s is at least equal to the number of <b>b</b>'s. <LI> (property ii) <IMG ALIGN=MIDDLE ALT="" SRC="img40.gif"></UL><b>(Strong) Inductive hypothesis:</b> Assume that properties i) and ii) are true for any <IMG ALIGN=MIDDLE ALT="" SRC="img41.gif"> where <IMG ALIGN=BOTTOM ALT="" SRC="img42.gif"> for all <IMG ALIGN=MIDDLE ALT="" SRC="img43.gif">.<b>Inductive step:</b> From this we need to show i) and ii) for any<IMG ALIGN=MIDDLE ALT="" SRC="img44.gif"> where <IMG ALIGN=BOTTOM ALT="" SRC="img45.gif">. There are two possibilities for the derivation of <b>x</b>:<UL><LI> <IMG ALIGN=BOTTOM ALT="" SRC="img46.gif"><P>Since this is a leftmost derivation, we know thatthat there exist some <b>y</b> and <b>z</b> where <IMG ALIGN=MIDDLE ALT="" SRC="img47.gif">.This means that <IMG ALIGN=MIDDLE ALT="" SRC="img48.gif"> and <IMG ALIGN=BOTTOM ALT="" SRC="img49.gif"> where<b>k+j=n</b>. Thus <b>y</b> and <b>z</b> have leftmost derivations from <b>S</b> ofless than <b>n+1</b> steps, so properties i) and ii) hold for <b>y</b> and <b>z</b> by the induction hypothesis.<P>(property i) Consider any prefix <IMG ALIGN=MIDDLE ALT="" SRC="img50.gif"> of <b>x=yz</b>. There are two possibilities:<UL><LI> <IMG ALIGN=MIDDLE ALT="" SRC="img51.gif"> is a prefix of <b>y</b>. Then <IMG ALIGN=MIDDLE ALT="" SRC="img52.gif"> by property i) for <b>y</b>.<LI> <IMG ALIGN=MIDDLE ALT="" SRC="img53.gif"> for some prefix of <b>z</b>, <IMG ALIGN=MIDDLE ALT="" SRC="img54.gif">. Then <IMG ALIGN=MIDDLE ALT="" SRC="img55.gif"> by property i) for <b>z</b> and property ii) for <b>y</b>.</UL>In each case of <IMG ALIGN=MIDDLE ALT="" SRC="img56.gif">, the number of <b>a</b>'s in <IMG ALIGN=MIDDLE ALT="" SRC="img57.gif"> is at leastthe number of <b>b</b>'s in <IMG ALIGN=MIDDLE ALT="" SRC="img58.gif">.<P>(property ii) Since property ii) holds for <b>y</b> and <b>z</b> we have <IMG ALIGN=MIDDLE ALT="" SRC="img59.gif">.So the number of <b>a</b>'s in <b>x</b> is equal to the number of <b>b</b>'s in <b>x</b>.<P><LI> <IMG ALIGN=BOTTOM ALT="" SRC="img60.gif">We know that there exists some <b>w</b> where<IMG ALIGN=BOTTOM ALT="" SRC="img61.gif">.This means that <IMG ALIGN=BOTTOM ALT="" SRC="img62.gif">.Thus <b>w</b> has a leftmost derivation from <b>S</b> ofless than <b>n+1</b> steps, so properties i) and ii) hold for <b>w</b> by the inductionhypothesis.<P>(property i) Consider any prefix <IMG ALIGN=MIDDLE ALT="" SRC="img63.gif"> of <b>x=awb</b>. There are three possibilities:<UL><LI> <IMG ALIGN=MIDDLE ALT="" SRC="img64.gif">. In this case, <IMG ALIGN=MIDDLE ALT="" SRC="img65.gif">.<LI> <IMG ALIGN=MIDDLE ALT="" SRC="img66.gif"> for some prefix of <b>w</b>, <IMG ALIGN=MIDDLE ALT="" SRC="img67.gif">.Then <IMG ALIGN=MIDDLE ALT="" SRC="img68.gif"> by property i) for <b>w</b>.<LI> <IMG ALIGN=MIDDLE ALT="" SRC="img69.gif">. Since property ii) holds for <b>w</b>, we have<IMG ALIGN=MIDDLE ALT="" SRC="img70.gif">.</UL>In each case of <IMG ALIGN=MIDDLE ALT="" SRC="img71.gif">, the number of <b>a</b>'s in <IMG ALIGN=MIDDLE ALT="" SRC="img72.gif"> is at leastthe number of <b>b</b>'s in <IMG ALIGN=MIDDLE ALT="" SRC="img73.gif">.<P>(property ii) Since property ii) holds for <b>w</b> we have <IMG ALIGN=MIDDLE ALT="" SRC="img74.gif">.So the number of <b>a</b>'s in <b>x</b> is equal to the number of <b>b</b>'s in <b>x</b>.</UL><P>Therefore, for any <IMG ALIGN=MIDDLE ALT="" SRC="img75.gif"> where <IMG ALIGN=BOTTOM ALT="" SRC="img76.gif">, propertiesi) and ii) hold by the principle of strong induction.<P></OL><BR> <HR><UL> <LI> <A NAME=tex2html3 HREF="node1.html#SECTION00010000000000000000"> About this document ... </A></UL><BR> <HR><A NAME=tex2html1 HREF="node1.html"><IMG ALIGN=BOTTOM ALT="next" SRC="http://www.cs.washington.edu/general/latex2html_icons//next_motif.gif"></A> <IMG ALIGN=BOTTOM ALT="up" SRC="http://www.cs.washington.edu/general/latex2html_icons//up_motif_gr.gif"> <IMG ALIGN=BOTTOM ALT="previous" SRC="http://www.cs.washington.edu/general/latex2html_icons//previous_motif_gr.gif"> <BR><B> Next:</B> <A NAME=tex2html2 HREF="node1.html"> About this document </A><BR> <HR> <P><BR> <HR><P><ADDRESS><I>James Fix <BR>Mon Jan 29 17:24:25 PST 1996</I></ADDRESS></BODY>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?