1) What is the difference between a compiler and an interpreter?
∙A compiler is a program that can read a program in one language - the source language - and translate it into an equivalent program in another language – the target language and report any errors in the source program that it detects during the translation process.
∙Interpreter directly executes the operations specified in the source program on inputs supplied by the user.
2) What are the advantages of:
(a) a compiler over an interpreter
a. The machine-language target program produced by a compiler is usually much faster than an interpreter at mapping inputs to outputs.
(b) an interpreter over a compiler?
b. An interpreter can usually give better error diagnostics than a compiler, because it execute
s the source program statement by statement.
3) What advantages are there to a language-processing system in which the compiler
produces assembly language rather than machine language?
The compiler may produce an assembly-language program as its output, because
assembly language is easier to produce as output and is easier to debug.
4.2.3 Design grammars for the following languages:
a) The set of all strings of 0s and 1s such that every 0 is immediately followed by at least 1.
S -> SS | 1 | 01 | ε
4.3.1 The following is a grammar for the regular expressions over symbols a and b o
nly, using + in place of | for unions, to avoid conflict with the use of vertical bar as meta-symbol in grammars:
    rexpr        ->  rexpr + rterm | rterm
    rterm        ->  rterm rfactor | rfactor
    rfactor      ->  rfactor * | rprimary
    rprimary  ->  a | b
a) Left factor this grammar.
    rexpr        ->  rexpr + rterm | rterm
    rterm        ->  rterm rfactor | rfactor
    rfactor      ->  rfactor * | rprimary
    rprimary  ->  a | b
b) Does left factoring make the grammar suitable for top-down parsing?
No, left recursion is still in the grammar.
c) In addition to left factoring, eliminate left recursion from the original grammar.
    rexpr        ->  rterm rexpr’
rexpr’      ->  + rterm rexpr | ε
    rterm        ->  rfactor rterm’
    rterm’      ->  rfactor rterm  | ε
    rfactor      ->  rprimary rfactor’
    rfactor’    ->  * rfactor’  | ε
    rprimary  ->  a | b
d) Is the resulting grammar suitable for top-down parsing?
Yes.
Exercise 4.4.1 For each of the following grammars, derive predictive parsers and show the parsing tables. You may left-factor and/or eliminate left-recursion from your grammars first.  A predictive parser may be derived by recursive decent or by the table driven approach.  Either way you must also show the predictive parse table.
a) The grammar of exercise 
4.2.2 a) S -> 0S1 | 01
This grammar has no left recursion.  It could possibly benefit from left factoring.  Here is the recursive decent PP code.
s() {
    match(‘0’);
    if (lookahead == ‘0’)
        s();
    match(‘1’);
}
Or
Left factoring the grammar first:
S -> 0S’
S’ -> S1 | 1
s() {
    match(‘0’); s’();
}
s’() {
    if (lookahead == ‘0’)
        s(); match(‘1’);
    else
        match(‘1’);
}
Now we will build the PP table
S -> 0S’
S’ -> S1 | 1
First(S) = {0}
First(S’) = {0, 1}
Follow(S) = {1, $}
Follow(S’) = {1, $}
truncated class file翻译
Non-Terminal
Input Symbol
0
1
$
S
S->0S’
S’
S’->S1
S’->1
The predictive parsing algorithm on page 227 (fig4.19 and 4.20) can use this table for non-recursive predictive parsing.

b) The grammar of exercise
4.2.2 b) S -> +SS | *SS | a with string +*aaa.
Left factoring does not apply and there is no left recursion to remove.
s() {
    if(lookahead == ‘+’)
        match(‘+’); s(); s();
    else if(lookahead == ‘*’)
        match(‘*’); s(); s();
    else if(lookahead == ‘a’)
        match(‘a’);
    else
        report(“syntax error”);
}
First(S) = {+, *, a}
Follow(S) = {$, +, *, a}
Non-Terminal
Input Symbol
+
*
a
$
S
S-> +SS
S->*SS
S->a
The predictive parsing algorithm on page 227 (fig4.19 and 4.20) can use this table for non-recursive predictive parsing.
5.1.1 a, b, c: Investigating GraphViz as a solution to presenting trees

 Extend the SDD of Fig. 5.4 to handle expressions as in Fig. 5.1:
1. L -> E N
1. L.val = E.syn
2. E -> F E'
1. E.syn = E'.syn
2. E'.inh = F.val
3. E' -> + T Esubone'
1. Esubone'.inh = E'.inh + T.syn
2. E'.syn = Esubone'.syn
4. T -> F T'
1. T'.inh = F.val
2. T.syn = T'.syn
5. T' -> * F Tsubone'
1. Tsubone'.inh = T'.inh * F.val
2. T'.syn = Tsubone'.syn
6. T' -> epsilon
1. T'.syn = T'.inh
7. E' -> epsilon
1. E'.syn = E'.inh
8. F -> digit
1. F.val = digit.lexval
9. F -> ( E )

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。