Describing Syntax and Semantics

Written on 17.36 by Unknown

We meet yet again through my blog and this time I'm gonna talk about my third assignment from Mr. Tri Djoko Wahjono, Ir, M.Sc. It is about "Describing Syntax and Semantics", the third chapter from Sebesta's Programming Language Concepts book, so i answered 5 questions from the review questions and 5 questions from the problem sets. So here is my answer for them : 


Review Questions :

1. Define syntax and semantics. 
  • Syntax is form of expressions, statements and program units in a programming language. while semantics is the meaning of the expressions, statements and program units in a programming language.

2. Who are language descriptions for?
  •  Language descriptions are for initial evaluators, implementors, and users

3. Describe the operation of a general language generator.
  • A language generator is a device that can be used to generate the sentences of a language. We can think of the generator as having a button that produces a sentence of the language every time it is pushed. Because the particular sentence that is produced by a generator when its button is pushed is unpredictable, a generator seems to be a device of limited usefulness as a language descriptor. For example, to determine the correct syntax of a particular statement using a compiler, the programmer can only submit a speculated version and note whether the compiler accepts it. On the other hand, it is often possible to determine whether the syntax of a particular statement is correct by comparing it with the structure of the generator.

4. Describe the operation of a general language recognizer. 
  • Suppose we have a language L that uses an alphabet of characters. To define L formally using the recognition method, we would need to construct a mechanism R, called a recognition device, capable of reading strings of characters from the alphabet . R would indicate whether a given input string was or was not in L. In effect, R would either accept or reject the given string. Such devices are like filters, separating legal sentences from those that are incorrectly formed. If R, when fed any string of characters over , accepts it only if it is in L, then R is a description of L. Because most useful languages are, for all practical purposes, infinite, this might seem like a lengthy and ineffective process. Recognition devices, however, are not used to enumerate all of the sentences of a language they have a different purpose. The syntax analysis part of a compiler is a recognizer for the language the compiler translates. In this role, the recognizer need not test all possible strings of characters from some set to determine whether each is in the language. Rather, it need only determine whether given programs are in the language. In effect then, the syntax analyzer determines whether the given programs are syntactically correct.

5. What is the difference between a sentence and a sentential form? 
  • A sentence is a sentential form that consist only terminal or lexemes while sentential form is a string that consist of derivations.


Problem Set :


1. The two mathematical models of language description are generation and recognition. Describe 
    how each can define the syntax of a programming language. 
  • The recognizer doesn't need to test all possible strings of characters from some set to determine whether each is in the language. Rather, it need only determine whether given programs are in the language. In effect then, the syntax analyzer determines whether the given programs are syntactically correct.
  • To determine the correct syntax of a particular statement using a compiler, the programmer can only submit a speculated version and note whether the compiler accepts it. On the other hand, it is often possible to determine whether the syntax of a particular statement is correct by comparing it with the structure of the generator.

2. Write EBNF descriptions for the following:
     a. A Java class definition header statement 
    • <class_head> ® {<modifier>} class <id> [extends class_name] [implements <interface_name> {, <interface_name>}] <modifier> ® public | abstract | final <class_head> ® {<modifier>} class <id> [extendsclass_name] [implements <interface_name> {, <interface_name>}] <modifier> ® public | abstract | final
     b. A Java method call statement
    • <for> -> for ‘(‘ [[<type>] <id> = <expr> {, [<type>] <id> = <expr>}] ; [<expr>] ; [<expr>{, <expr>}] ‘)’ ‘{‘ <stmt_list> ‘}’
     c. A C switch statement 
    • <stmt> -> switch ( <int expr> ) {
    • case <int const> : { <stmt> ; }
    • { case <int const> : { <stmt> ; }}
    • [ default : { <stmt> ; } ]}
     d. A C union definition
    • <union_defn> -> union <var_list> <union_identifier>;
    • <var_list> -> <list_of_data-type specifier> <var>
    • <list_of_data-type specifier> -> int | float | long |char | double
    • <union_identifier> -> <var>
     e. C float literals 
    • <float-literal> –> <real> <suffix>
    • | <real> <exponent> <suffix>
    • | <integer> <exponent> <suffix>
3. Rewrite the BNF of Example 3.4 to give + precedence over * and force + to be right associative. 
  • <assign> -> <id> = <expr>
  • <id> -> A | B | C
  • <expr> -> <expr> – <term>
  • | <term>
  • <term> -> <term> / <factor>
  • | <factor>
  • <factor> -> ( <expr> )
  • | <id>

4. Rewrite the BNF of Example 3.4 to add the ++ and -- unary operators of Java. 
  • <assign> -> <id> = <expr>
  • <id> -> A | B | C
  • <expr> += <term>
  • | <term>
  • <term> *= <factor>
  • | <factor>
  • <factor> -> ( <expr> )
  • | <id>
5. Write a BNF description of the Boolean expressions of Java, including the three operators &&, ||, 
    and ! and the relational expressions. 
  • <Boolean_expr> -> <Boolean_expression> || <Boolean_term> | <Boolean_term>
  • <Boolean_term> -> <Boolean_term> && <Boolean_factor> | <Boolean_factor>
  • <Boolean_factor> -> id | ! <Boolean_factor> | ( <Boolean_expr> ) | <relation_expr>
  • <relation_expr> -> id = = id | id != id | id < id | id <= id | id >= id | id > id

This is my answer for the third chapter review questions and problem sets.

Posted in , , , , | 0 komentar

Evolution of the Major Programming Languages

Written on 18.59 by Unknown

      Hello, welcome back to my blog. This is my second assignment from the same lecture. This time i was required to answer the Review Question and Problem Set from the second chapter of Sebesta's Programming Language Concepts book.

 Here is the answer for the review questions :

         1.       In what year was Plankalkül designed? In what year was that design published? 
·       It was designed in 1945 and the design was published 27 years later or on 1972.

         2.       What two common data structures were included in Plankalkül?
·       The 2 common data structures were arrays and records.

         3.       How were the pseudocodes of the early 1950s implemented?
·       The Pseudocodes were implemented by a pure interpreter.

         4.      Speedcoding was invented to overcome two significant shortcomings of the
          computer hardware of the early 1950s. What were they?
·       The shortcomings were the lack of floating point and the lack of automatic incrementing address registers.

         5.       Why was the slowness of interpretation of programs acceptable in the early 1950s?
·       One of the primary reasons why the slowness of interpretive systems was tolerated from the late 1940s to the mid-1950s was the lack of floating-point hardware in the available computers. All floating-point operations had to be simulated in software, a very time-consuming process. Because so much processor time was spent in software floating-point processing, the overhead of interpretation and the simulation of indexing were relatively insignificant. 


    Here is the answer for the problem set questions :

    1.    What features of Plankalkül do you think would have had the greatest influence on FORTRAN 0 if the FORTRAN designers had been familiar with Plankalkül?
    ·       The feature of Plankalkül that can have a great influenced on Fortran 0 if the Fortran designers had been familiar with Plankalkül is the inclusion of mathematical expressions showing the current relationships between program variables, which could make Fortran 0 compute floating point more faster.

    2.     Determine the capabilities of Backus’s 701 Speedcoding system, and compare them with those of a contemporary programmable hand calculator.
    ·       The Speedcoding interpreter effectively converted the 701 to a virtual three-address floating-point calculator. The system included pseudo instructions for the four arithmetic operations on floating-point data, as well as operations such as square root, sine, arc tangent, exponent, and logarithm. Conditional and unconditional branches and input/output conversions were also part of the virtual architecture. Speedcoding included the novel facility of automatically incrementing address registers. This facility did not appear in hardware until the UNIVAC 1107 computers of 1962. Because of such features, matrix multiplication could be done in 12 Speedcoding instructions. Backus claimed that problems that could take two weeks to program in machine code could be programmed in a few hours using Speedcoding. It means that Backus’s 701 speedcoding system can solve arithmetic problem much more faster than using programmable hand calculator.


    3.     Write a short history of the A-0, A-1, and A-2 systems designed by Grace Hopper and her associates.
    ·       Between 1951 and 1953, a team led by Grace Hopper at UNIVAC developed a series of “compiling” systems named A-0, A-1, and A-2 that expanded a pseudo- code into machine code subprograms in the same way as macros are expanded into assembly language. The pseudo-code source for these “compilers” was still quite primitive, although even this was a great improvement over machine code because it made source programs much shorter. Wilkes (1952) independently suggested a similar process. Maurice V. Wilkes (also at Cambridge) extended the idea to design an assembly program that could combine chosen subroutines and allocate storage (Wilkes et al., 1951, 1957).

    4.     As a research project, compare the facilities of FORTRAN 0 with those of the Laning and Zierler system.
    ·       The Laning and Zierler system (Laning and Zierler, 1954) was the first algebraic translation system to be implemented. By algebraic, it means that it translated arithmetic expressions, used separately coded subprograms to compute transcendental functions (e.g., sine and logarithm), and included arrays. Such facilities was not found in Fortran 0 that still hadn’t used interpretation on algebraic translation and arrays system. In fact the facilities in Laning and Zierler system was more superior to Fortran 0, but it was never escaped MIT which is a shame.


    5.     Which of the three original goals of the ALGOL design committee, in your opinion, was most difficult to achieve at that time?
    •       “It should be possible to use the language for the description of algorithms in printed publications” was the most difficult goal to achieve at that time because it was something that entirely new to the computer business, at that time publication for algorithm in the human language is hard to understand since it is a new language that they never used before so they need to know how the language work first.

    Posted in , , , | 0 komentar