1. Consider the grammar given below <Group> ::= [ <One>, <Group> ] | <One> <One>

Question

1. Consider the grammar given below

<Group> ::= [ <One>, <Group> ] | <One>

<One> ::= <Var> | ( <Group> )

<Var> ::= a | b | c

What is the start symbol? (The start symbol you choose should allow the grammar to parse the most input sentences)

Draw parse tree for the input string [(a), [b, c]].

2. Write a BNF grammar for Java style switch statements <SwitchStmt>.

Assume that there are definitions for the non-terminal <Exp> for any expression, Const for any constant, and Stmt for any statement.

Explanation / Answer

Answer(1.1) The start symbol is <Group>.
       To explain, why <Group> should be the start symbol, we should first understand what each rule will be able

to parse.
   

   The first part of first rule is <Group> ::= [ <One>, <Group> ], so it can parse all the inputs sentences with-in the third-brackets '[' ']'.
       The second part of the first rule is <Group> :: <one>, so it can parse all the input sentences which are accepted by non-terminal <One>.

        Now, the second rule is <One> ::= <Var> | ( <Group> )
        First part of this second rule is <One> ::= <Var>, so all the variables will be parsed by it.
        Second part of this second rule is <One> ::= ( <Group> ), so all the sentences within parenthesis '(' ')' will be accepted by it.

        So, effectively if <Group> is made the start symbol, then we can parse
        (a) part of input sentences in third-bracket '[' ']'
        (b) sentences accepted by non-terminal <One>. This non-terminal accepts all the part of input sentences in parenthesis '(' ')' and the terminals 'a' 'b' 'c'.


Answer(1.2) Parse Tree for the input string [(a), [b,c]] is as follows:
                             <Group>
                /        |                                              
                [          <one>          ,        <Group>               ]
                        /      |               / |       
                    ( <Group> )          [ <One> , <Group> ]
                             |                   |       |
                        <One>                  <Var>   <One>
                           |                             |           |
                           <Var>                b        <Var>
                           |                                   |
                            a                                c
                           
                [      (      a       )    ,   [    b ,    c    ]   ]    
               
               

Answer(2) BNF grammar for Java style switch statements is as follows:
            <SwitchStmt> ::= <Switch-Expression> <Switch-Body>
            <Switch-Expression> ::= switch ( <Exp> )
            <Switch-Body> ::= { <CaseItem-List> }
            <CaseItem-List> ::= <CaseItem-List> <Case-Item>
                              | <default-Case-Item>  
            <Case-Item>    ::= case ( <Const> ) : <Stmt>
            <default-Case-Item> ::= default : <Stmt>

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.