Question

1. For this question, assume a simple programming language (SPL) has been designed to write a straight-line program (SLP). Programs written in this simple programming language, such as the sample program P1 shown below, allow the implementation of only statements and expressions, but no loops or if-statements. Note the print function will take an expression list as its arguments.

       Program P1:
           a := 2 + 5; b := (print (a, a-1), 7 * a) ; print (b)
      

Execution of this program will yield output
                       7 6

49

a.) What is the grammar being used to specify the syntax of this language?

b.) What is a concrete syntax of the program? (Hint: parse tree)

Answer 1

As according to the question asked here, the answer can be divided into two main parts with two sub-parts. But before getting started lets recall some basic understanding first,

The output part of a program or generally programming language is structurized as

datatype variable_name = value or expression

Lets understand it better with Javascript as example in hand, as according to the syntax definition of JS

• identifier variable_name "is equal to" the value to be assigned to the variable.

i.e let a = 5 or let a = 5+5 or let a = return [expression] (expression = operations on numbers or variables being used in the program)

As far as the concern about js,  the concrete syntax tree(CST) of the langauge can be understand by the given picture

• Blue text — CST Tokens.
• White text in blue blocks — CST Nodes (their structure is equal to an AST).
• Blue lines — CST Structure.
• Red lined — AST Links.

Source:- Github (https://raw.githubusercontent.com/cst/cst/master/docs/cst-example.png)

Explaination of CST:-

Where every element of the program contains body(that can be variable with value, function with several variables and values or expressions) as defined in the image. The CST of the language defines the set of rules which should be followed by the programmer in order to make the program run, if not followed the CST rules the program will not be able to run, as the compiler assigned to the language will not be able to recognise what the "Statement is meant for" hence will result in error or mis interpretation of the program"

For Example :- " Punctuator or Terminator in js( ; )" represents the end of line in JS, if not applied the compiler will not be able to recognise the line ending, and will result in error... (as per the previous formats of JS, not with ES6)

[*Note :- CST is the outline of the programming language in general terms ]

Explaination Of Grammar:-

• "A grammar is a formal description of a language that can be used to recognize its structure."

In simple terms is a list of rules that define how each construct can be composed. For example, a rule for an for statement could specify that it must starts with the “for” keyword, followed by a left parenthesis, an expression(initialization;counter;condition), a right parenthesis and a statement under its block starting with { and ending with }

Answer Summar:- As per the concern about the answer to the question:-

BNF(Backus-Naur Form)

• Notation technique for context free grammer (CFG)
• specify the syntax of the language
• <symbol>; = Expression 1/express2/eXPRESS3 , where <symbol> is non terminals & Expressions are sequence of symbols & this can be a combination of terminals as well as non terminals
• Representing Grammer as S-> aBA B->bB/^ C->a/b

So, Answer to (A) The Grammer being used is Context Free Grammer(CFG) & the concrete syntax to the language will be definite or approximate to the image defined above.

i.e Program->Body->Expression(Value & Operation)->Loop->Identifier->Literal->Terminator