Syntax Flashcards
syntax
the form or structure of the expressions, statements and program units (formal method to describe how to determine a statement’s set membership in a Language)
semantics
the meaning of the expressions, statements, and program units
grammar
formal description of a Language
sentence
a string of characters over some alphabet
language
a set of sentences (characterized by the set of all valid statements / strings in that language.
The cardinality of this set is potentially infinite)
lexeme
lowest level syntactic unit of a language
token
category of lexemes
recognizers; generators
grammars can be formally utilized in two distinct ways: for ____ and for ___. (two approaches to describing syntax)
Recognition device
___ device reads input strings over the alphabet of the language and decides whether the input strings belong to the language (i.e.syntax analysis part of a compiler)
Generators
A device that generates sentences of a language (one can determine if the syntax of a particular sentence is syntactically correct by comparing it to the structure of the generator
grammars
what is the formal language-generation mechanism commonly used to describe the syntax of programming languages
Backus-Naur Form (BNF) is equivalent to
Context-Free Grammars
Context Free Grammar syntax
Grammar = (Start symbol, set of Non-terminals, set of Terminals, set of Production Rules)
define non-terminal symbols
abstractions are used to represent classes of syntactic structures; they act like syntactic variables (often enclosed in angle brackets <>)
define terminal symbols
they are lexemes
Each Production Rule has:
•a left-hand side (LHS), which is a ___ ___, and
•a right-hand side (RHS), which is a ___ of ___ and/or ___
single non-terminal; string of terminals and/or non-terminals
define derivation (given a set of grammar rules know how to give derivation)
determines the order that nodes of a parse tree are built
repeated application of rules, starting with the start symbol and ending with a sentence with all terminal symbol
define sentential form
every string of symbols in a derivation
valid sentence
a sentential form that as only terminal symbols
define leftmost derivation
derivation in which the leftmost nonterminal in each sentential form is the one that is expanded
(expand leftmost nonterminal first)
define rightmost derivation
expand rightmost nonterminal first
define parse tree
hierarchical representation of a derivation
a grammar is ambiguous if and only if:
it generates a sentential form that has two or more distinct parse tree
which language has grammar based on predicate logic
LOGLAN (logical languages, also include Lojban and Ceqli)
how can we eliminate ambiguity?
if we use the parse tree to indicate precedence levels of the operators
Be able to use recursive BNF rules to describe lists of arbitrary length means:
be able to describe the list of potential sentences in the language generated by a particular grammar
Explain what deep syntax structure and surface syntax structure are
Sentences can be either passive or active and that difference lies in their surface structure.
But their deep structure may be the same, for example NP+V+NP
What is structural ambiguity?
Sentences that can be understood in more than one way.
What are “recursive rules”?
Syntactic rules that can be applied more than once in generating a structure.
Why Semantic roles
Some words may be more difficult to find the semantic meaning for than table horse etc. Words as warning, advice, threat. If we look at words as having roles in a sentence instead of containers of meaning this becomes easier.
