Language Syntax and Symantics
Written on Monday, May 05, 2008 by Ennah, the comsci student
My Research 3. I found all of the answer in Sebasta's book. This research helped me in my 2nd machine problem, checking grammars.
1. Define: Language, syntax, semantics, lexemes, tokens.
2. Describe the operations of a general language recognizer and a general language generator.
3. What is the difference between a sentence & a sentence form?
4. What is grammar? Describe CFG, BNF, EBNF.
5. Differentiate between a synthesized and an inherited attribute.
6. What is an attribute grammar? What is its primary purpose?
7. Differentiate between a static and dynamic semantics.
8. Discuss the 3 primary methods of semantic description: operational, axiomatic & denotational.
Answers
1. Define: Language, syntax, semantics, lexemes, tokens.
Language - is set of sentences or strings of characters over some alphabet.
Syntax - is the form or structure of the expressions, statements and program units.
Semantics - is the meaning of expressions, statements and program units.
Lexeme - is the lowest level syntactic unit of a language (e.g. *, sum, begin)
Token - a category of a lexeme (e.g. identifier, equal_sign)
2. Describe the operations of a general language recognizer and a general language generator.
A general language recognizer is a recognition device capable of reading strings of characters from the alphabet. It would analyze the given string and it would either accept or reject the string based from the language given. These recognition devices are like filters separating correct sentences from those that are incorrectly. A recognizer is used in the syntax analysis part of the compiler. In this role, the recognizer need not test all possible strings of characters from some set to determine whether each is in the language. The syntax analyzer just determines whether the given programs are syntactically correct.
A general language generator is a device that can be used to generate the sentences of the language. It generates unpredictable sentences which makes a generator seems to be a device of limited usefulness as language descriptor. However, people prefer certain forms of generators over recognizer because they can be more easily read and understand them. By contrast, the syntax-checking portion of the compiler which is a language recognizer is not as useful a language descriptor for programmers because it can be used in a trial-and-error mode. For example, to determine the correct syntax of a particular statement using the compiler, the programmer can only submit a guessed-at version and see if 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.
3. What is the difference between a sentence & a sentence form?
A sentence is a sentential form that has only terminal symbols. A sentence form is every string of symbols in the derivation.
4. What is grammar? Describe CFG, BNF, EBNF.
Grammar is a formal language generation mechanism that is commonly used to describe the syntax of programming languages. A grammar is a 4-tuple (N, T, S, P), whereN is a set of nonterminal symbolsT is a set of terminal symbols S is the start symbolP is a set of productions (also called rewrite rules)
Example of Grammar
Nonterminals = {S, A}
Terminals = {a, b}
Start symbol = SP = { S --> bA, S --> aA, A --> aA, A --> b}
A sentence consists entirely of terminal symbols (in this grammar, a’s and b’s)
The productions can be used to generate sentences, starting with a rule for the start symbol (S).
Context Free Grammars (CFG) is a notation whose productions take the form
A -->a, where A is a single nonterminal symbol and a is any string of terminals and/or nonterminals. Context-free grammars are used to describe the syntax of modern programming languages.
Backus Naur Form (BNF) is a metalanguage, a language used to describe another language. In BNF, rules are used to describe the syntax of a language. There is at least one rule for each language abstraction (nonterminal). BNF is equivalent to CFGs.
Extended Backus Naur Form (EBNF) is an extended version of BNF because of BNF’s few minor inconveniences. The extensions do not enhance the descriptive power of BNF; they only increase its readability and writability. Three versions are commonly included in the various versions of EBNF: Optional parts are placed in brackets([]) ---> ident [ ( )Put alternatives in parentheses and separate them with vertical bars ---> (+|-) constPut repetitions (0 or more) in braces ({}) ---> { , }
5. Differentiate between a synthesized and an inherited attribute.
The synthesized attributes are the result of the attribute evaluation rules, and may also use the values of the inherited attributes. The inherited attributes are passed down from parent nodes.In some approaches, synthesized attributes are used to pass semantic information up the parse tree, while inherited attributes help pass semantic information down it.
For instance, when constructing a language translation tool, such as a compiler, it may be used to assign semantic values to syntax constructions. Also, it is possible to validate semantic checks associated with a grammar, representing the rules of a language not explicitly imparted by the syntax.
6. What is an attribute grammar? What is its primary purpose?
An attribute grammar is a device used to describe more of the structure of a programming language than is possible with a context-free grammar. An attribute grammar is an extension to a context-free grammar. The primary purpose of an attribute grammar is it allows certain language rules to be described, such as type of compatibility. An attribute grammar is a formal way to define attributes for the productions of a formal grammar, associating these attributes to values. The evaluation occurs in the nodes of the abstract syntax tree, when the language is processed by some parser or compiler.
7. Differentiate between a static and dynamic semantics.
Static semantics is more on the legal forms of programs (syntax rather symantics) and is only indirectly related to the meaning of the programs during execution. Static semantics is so named because the analysis required to check these specifications can be done at compile time. In many cases, the semantic rules of language state its type constraints.
Dynamic semantics is describing the meaning of the programs. Programmers need to know precisely what statements of a language do. Compile writers determine the semantics of a language for which they are writing compilers from English descriptions
8. Discuss the 3 primary methods of semantic description: operational, axiomatic & denotational.
Operational Semantics is a concept to describe the meaning of the program by executing its statements on the machine, either real or simulated. The changes that occur in the machine’s state when it executes a given statement define the meaning of that statement.
Axiomatic Semantics is a concept that is in conjunction with the development of a method to prove the correctness of a program. Such correctness proofs, when they can be constructed, show that a program performs the computation described by its specifications. In a proof, each statement of a program is both preceded and followed by a logical expression that specifies constraints on program variables. These, rather than the entire state of an abstract machine (as with operational semantics), are used to specify the meaning of the statement. The notation used to describe constraints, indeed the language of axiomatic semantics, is predicate calculus.
Denotational Semantics is a method of describing the meaning of the programs solidly based on recursive function theory. The fundamental concept of the denotational semantics is to define for each language entity both a mathematical object and a function that maps instances of that entity onto instances of mathematical object. Because the objects are rigorously defined, they represent the exact meaning of their corresponding entities. The idea is based on the fact that there are rigorous ways of manipulating mathematical objects but not for programming constructs. The difficulty of this method lies in creating the objects and the mapping functions. The method is named denotational because the mathematical objects denote the meaning of their corresponding syntactic entities.
1. Define: Language, syntax, semantics, lexemes, tokens.
2. Describe the operations of a general language recognizer and a general language generator.
3. What is the difference between a sentence & a sentence form?
4. What is grammar? Describe CFG, BNF, EBNF.
5. Differentiate between a synthesized and an inherited attribute.
6. What is an attribute grammar? What is its primary purpose?
7. Differentiate between a static and dynamic semantics.
8. Discuss the 3 primary methods of semantic description: operational, axiomatic & denotational.
Answers
1. Define: Language, syntax, semantics, lexemes, tokens.
Language - is set of sentences or strings of characters over some alphabet.
Syntax - is the form or structure of the expressions, statements and program units.
Semantics - is the meaning of expressions, statements and program units.
Lexeme - is the lowest level syntactic unit of a language (e.g. *, sum, begin)
Token - a category of a lexeme (e.g. identifier, equal_sign)
2. Describe the operations of a general language recognizer and a general language generator.
A general language recognizer is a recognition device capable of reading strings of characters from the alphabet. It would analyze the given string and it would either accept or reject the string based from the language given. These recognition devices are like filters separating correct sentences from those that are incorrectly. A recognizer is used in the syntax analysis part of the compiler. In this role, the recognizer need not test all possible strings of characters from some set to determine whether each is in the language. The syntax analyzer just determines whether the given programs are syntactically correct.
A general language generator is a device that can be used to generate the sentences of the language. It generates unpredictable sentences which makes a generator seems to be a device of limited usefulness as language descriptor. However, people prefer certain forms of generators over recognizer because they can be more easily read and understand them. By contrast, the syntax-checking portion of the compiler which is a language recognizer is not as useful a language descriptor for programmers because it can be used in a trial-and-error mode. For example, to determine the correct syntax of a particular statement using the compiler, the programmer can only submit a guessed-at version and see if 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.
3. What is the difference between a sentence & a sentence form?
A sentence is a sentential form that has only terminal symbols. A sentence form is every string of symbols in the derivation.
4. What is grammar? Describe CFG, BNF, EBNF.
Grammar is a formal language generation mechanism that is commonly used to describe the syntax of programming languages. A grammar is a 4-tuple (N, T, S, P), whereN is a set of nonterminal symbolsT is a set of terminal symbols S is the start symbolP is a set of productions (also called rewrite rules)
Example of Grammar
Nonterminals = {S, A}
Terminals = {a, b}
Start symbol = SP = { S --> bA, S --> aA, A --> aA, A --> b}
A sentence consists entirely of terminal symbols (in this grammar, a’s and b’s)
The productions can be used to generate sentences, starting with a rule for the start symbol (S).
Context Free Grammars (CFG) is a notation whose productions take the form
A -->a, where A is a single nonterminal symbol and a is any string of terminals and/or nonterminals. Context-free grammars are used to describe the syntax of modern programming languages.
Backus Naur Form (BNF) is a metalanguage, a language used to describe another language. In BNF, rules are used to describe the syntax of a language. There is at least one rule for each language abstraction (nonterminal). BNF is equivalent to CFGs.
Extended Backus Naur Form (EBNF) is an extended version of BNF because of BNF’s few minor inconveniences. The extensions do not enhance the descriptive power of BNF; they only increase its readability and writability. Three versions are commonly included in the various versions of EBNF: Optional parts are placed in brackets([]) ---> ident [ ( )Put alternatives in parentheses and separate them with vertical bars ---> (+|-) constPut repetitions (0 or more) in braces ({}) ---> { , }
5. Differentiate between a synthesized and an inherited attribute.
The synthesized attributes are the result of the attribute evaluation rules, and may also use the values of the inherited attributes. The inherited attributes are passed down from parent nodes.In some approaches, synthesized attributes are used to pass semantic information up the parse tree, while inherited attributes help pass semantic information down it.
For instance, when constructing a language translation tool, such as a compiler, it may be used to assign semantic values to syntax constructions. Also, it is possible to validate semantic checks associated with a grammar, representing the rules of a language not explicitly imparted by the syntax.
6. What is an attribute grammar? What is its primary purpose?
An attribute grammar is a device used to describe more of the structure of a programming language than is possible with a context-free grammar. An attribute grammar is an extension to a context-free grammar. The primary purpose of an attribute grammar is it allows certain language rules to be described, such as type of compatibility. An attribute grammar is a formal way to define attributes for the productions of a formal grammar, associating these attributes to values. The evaluation occurs in the nodes of the abstract syntax tree, when the language is processed by some parser or compiler.
7. Differentiate between a static and dynamic semantics.
Static semantics is more on the legal forms of programs (syntax rather symantics) and is only indirectly related to the meaning of the programs during execution. Static semantics is so named because the analysis required to check these specifications can be done at compile time. In many cases, the semantic rules of language state its type constraints.
Dynamic semantics is describing the meaning of the programs. Programmers need to know precisely what statements of a language do. Compile writers determine the semantics of a language for which they are writing compilers from English descriptions
8. Discuss the 3 primary methods of semantic description: operational, axiomatic & denotational.
Operational Semantics is a concept to describe the meaning of the program by executing its statements on the machine, either real or simulated. The changes that occur in the machine’s state when it executes a given statement define the meaning of that statement.
Axiomatic Semantics is a concept that is in conjunction with the development of a method to prove the correctness of a program. Such correctness proofs, when they can be constructed, show that a program performs the computation described by its specifications. In a proof, each statement of a program is both preceded and followed by a logical expression that specifies constraints on program variables. These, rather than the entire state of an abstract machine (as with operational semantics), are used to specify the meaning of the statement. The notation used to describe constraints, indeed the language of axiomatic semantics, is predicate calculus.
Denotational Semantics is a method of describing the meaning of the programs solidly based on recursive function theory. The fundamental concept of the denotational semantics is to define for each language entity both a mathematical object and a function that maps instances of that entity onto instances of mathematical object. Because the objects are rigorously defined, they represent the exact meaning of their corresponding entities. The idea is based on the fact that there are rigorous ways of manipulating mathematical objects but not for programming constructs. The difficulty of this method lies in creating the objects and the mapping functions. The method is named denotational because the mathematical objects denote the meaning of their corresponding syntactic entities.
If you enjoyed this post Subscribe to our feed
.jpg)