Transcription of Solutions to Written Assignment 2 - Stanford University
{{id}} {{{paragraph}}}
Example: bachelor of science
Solutions to Written Assignment 2 - Stanford University
CS 143 CompilersHandout 7 Solutions to Written Assignment 21. Give a context-free grammar (CFG) for each of the following languages over the alphabet ={a,b}:(a) All strings in the languageL:{anbma2n|n,m 0}S aSaa|BB bB| (b) All nonempty strings that start and end with the same aXa|bXb|a|bX aX|bX| (c) All strings with more a s than b Aa|MS|SMAA Aa| M |MM|bMa|aMb(d) All palindromes (a palindrome is a string that reads the same forwards and backwards).S aSa|bSb|a|b| 2. A history major taking CS143 decided to write a rudimentary CFG to parse the roman nu-merals 1-99 (i,ii,iii,iv,v.)
E0! +Ej T ! FT0 T0! Tj F ! PF0 F0! *F0 j P ! (E) ja jb jep (a)Give the rst and follow sets for each non-terminal. The First and Follow sets of the non-terminals are as follows. ... Bj$ 10 0$0 2Follow(B) reduceB!S;B fBj$ 3 0$0 2Follow(S) reduceS!fB Sj$ 4 …
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: