[PL] Introduction to Programming Languages Exercise 6

Exercise 6.1

Consider the following concrete syntax:

<expr> 	  ::= <num> 
			| "{" "+" <expr> <expr> "}" 
        	| "{" "*" <expr> <expr> "}" 
        	| "{" "let" "{" <id> <expr> "}" <expr> "}" 
        	| <id> 

Describe whether each of the following is expr and why. <id> consists of one or more latin alphabets (a-z, A-Z), and <num> consists of one or more digits (0-9). Assume that it is allowed to add whitespaces among terminals freely.

1. {let {x 5} {+ 8 {* x 2 3}}}
   No

                                         x ∈ <id>  2 3 ∉ <expr>
                                         ------------------------
             5 ∈ <num>    8 ∈ <num> 	{* x 2 3} ∉ <expr>
             ----------   ---------------------------------
x ∈ <id>	5 ∈ <expr>	{+ 8 {* x 2 3}} ∉ <expr>
-------------------------------------------------
{let {x 5} {+ 8 {* x 2 3}}} ∉ <expr>

2. {with {x 0} {with {x 7}}}
   No

error
----------------------------------
{with {x 0} {with {x 7}}} ∉ <expr>

3. {let {3 5} {+ 8 {- x 2}}}
   No

3 ∉ <id>	
----------------------------------
{let {3 5} {+ 8 {- x 2}}} ∉ <expr>

4. {let {3 y} {+ 8 {* x 2}}}
   No

3 ∉ <id>
-------------------------
{let {3 y} {+ 8 {* x 2}}}

5. {let {x y} {+ 8 {* x 2}}}
   Yes

                                        x ∈ <id>	2 ∈ <num>
                                       ----------   -----------
                           8 ∈ <num>   x ∈ <expr>  2 ∈ <expr>
                          -----------  ------------------------  
             y ∈ <id>	  8	∈ <expr>         {* x 2} ∈ <expr>
            ----------    -------------------------------------
x ∈ <id>	y ∈ <expr> 	{+ 8 {* x 2}} ∈ <expr>
-------------------------------------------------
{let {x y} {+ 8 {* x 2}}} ∈ <expr>

Exercise 6.2

Consider the following concrete syntax:

<ice-cream>   ::= "sprinkles" "on" <ice-cream> 
				| "cherry" "on" <ice-cream> 
            	| "scoop" "of" <flavor> "on" <ice-cream> 
            	| "sugar-cone" 
            	| "waffle-cone" 
                
<flavor> 	  ::= "vanilla" 
				| "lettuce" 

Assume that it is allowed to add whitespaces among terminals freely. Describe whether each of the following is <ice-cream> and why.

1. sprinkles
   No

sprinkles ∉ <ice-cream>

2. sugar-cone
   Yes

sugar-cone ∈ <ice-cream>

3. vanilla
   No

vanilla ∉ <ice-cream>

4. scoop of vanilla on waffle-cone
   Yes

vanilla ∈ <flavor>		waffle-cone ∈ <ice-cream>
---------------------------------------------------
scoop of vanilla on waffle-cone ∈ <ice-cream>

5. sprinkles on lettuce on waffle-cone
   No

lettuce on waffle-cone ∉ <ice-cream>
-------------------------------------------------
sprinkles on lettuce on waffle-cone ∉ <ice-cream>

6. scoop of vanilla on sprinkles on waffle-cone
   Yes

            	    	 waffle-cone ∈ <ice-cream>
                        ---------------------------------------
vanilla ∈ <flavor>		sprinkles on waffle-cone ∈ <ice-cream>
---------------------------------------------------------------
scoop of vanilla on sprinkles on waffle-cone ∈ <ice-cream>

7. cherry on scoop of lettuce on scoop of vanilla on sugar-cone
   Yes

                     vanilla ∈ <flavor>		sugar-cone ∈ <ice-cream>
                     --------------------------------------------
lettuce	∈ <flavor>	scoop of vanilla on sugar-cone ∈ <ice-cream>
-----------------------------------------------------------------
scoop of lettuce on scoop of vanilla on sugar-cone ∈ <ice-cream>
---------------------------------------------------------------------------
cherry on scoop of lettuce on scoop of vanilla on sugar-cone ∈ <ice-cream>

Exercise 6.3

Consider the following concrete syntax:

espresso ∈ <coffee> 


e1 ∈ <milk> 		e2 ∈ <coffee> 
----------------------------------
e1 "on" e2 ∈ <coffee> 


e1 ∈ <coffee> 		e2 ∈ <milk> 
----------------------------------
e1 "on" e2 ∈ <coffee> 


e1 ∈ <flavor> 		e2 ∈ <coffee> 
----------------------------------
e1 "on" e2 ∈ <coffee> 



"milk-foam" ∈ <milk> 


"caramel" ∈ <flavor> 


"cocoa-powder" ∈ <flavor> 


"steamed-milk" ∈ <milk> 


"cinnamon" ∈ <flavor> 


"chocolate-syrup" ∈ <flavor> 

Assume that it is allowed to add whitespaces among terminals freely. Describe whether each of the following is <coffee> and why.

1. caramel latte macchiato
   No

caramel latte macchiato ∉ <coffee>

2. espresso
   Yes

espresso ∈ <coffee>

3. steamed-milk on caramel on milk-foam on espresso
   Yes

											milk-foam ∈ <coffee>	 espresso ∈ <coffee>
											----------------------------------------------
						caramel ∈ <flavor>	milk-foam on espresso ∈ <coffee>
						---------------------------------------------
steamed-milk ∈ <milk> 	caramel on milk-foam on espresso ∈ <coffee>
------------------------------------------------------------
steamed-milk on caramel on milk-foam on espresso ∈ <coffee>

4. chocolate-syrup on cocoa-powder on cinnamon on milk-foam on steamed-milk on espresso
   Yes

																		       steamed-milk ∈ <milk>	espresso ∈ <coffee> 
                                                                               ------------------------------------
														 milk-foam ∈ <milk> 	steamed-milk on espresso ∈ <coffee> 
                                                         ---------------------------------------------------------------------------
														 cinnamon ∈ <flavor>	milk-foam on steamed-milk on espresso ∈ <coffee> 
                                                         -------------------------------------------------------------
                             cocoa-powder ∈ <flavor>	cinnamon on milk-foam on steamed-milk on espresso ∈ <coffee> 
                             ------------------------------------------------------------------------------
chocolate-syrup	∈ <flavor>	cocoa-powder on cinnamon on milk-foam on steamed-milk on espresso ∈ <coffee> 
------------------------------------------------------------------------------------------------
chocolate-syrup on cocoa-powder on cinnamon on milk-foam on steamed-milk on espresso ∈ <coffee> 

5. steamed-milk on espresso on chocolate-syrup
   No

						 espresso ∈ <coffee>		chocolate-syrup ∉ <milk>
                         ----------------------------------------------------
steamed-milk ∈ <milk>	espresso on chocolate-syrup ∉ <coffee>
---------------------------------------------------------------
steamed-milk on espresso on chocolate-syrup ∉ <coffee>

6. cocoa-powder on milk-foam on steamed-milk on espresso
   Yes

								                steamed-milk ∈ <milk>	espresso ∈ <coffee>
                                                --------------------------------------------
							milk-foam ∈ <milk>	steamed-milk on espresso ∈ <coffee>
							---------------------------------------
cocoa-powder ∈ <flavor>	milk-foam on steamed-milk on espresso ∈ <coffee>
--------------------------------------------------------
cocoa-powder on milk-foam on steamed-milk on espresso ∈ <coffee>