Language Structure and Regular Expressions

Chapter Objectives

• Introduce syntax and semantics needed to define a language
• Describe formal methods for defining the syntax of a programming language
• Establish understanding of regular languages, expressions, and grammars
• Discuss the use of the Backus-Naur Form to define grammars
• Establish an understanding of context-free languages and grammars
• Introduce the role of context in programming languages and the challenges in modeling context

Introduction to Formal Languages

• Alphabet: A finite set of symbols, denoted by Σ, for example {a, b, c}.
• Strings: Combinations of symbols (characters) over an alphabet.
  • If the alphabet (Σ) = {a, b, c}, then examples of strings include: a, aa, ab, abc, aba, bb, etc.
• The Kleene closure of an alphabet, denoted Σ*, represents the set of all possible strings over that alphabet.
  • While an alphabet (Σ) is always finite, its Kleene closure (Σ*) is always infinite.
  • Σ* always contains a null character or ε.
• A formal language (L) is a set of strings, specifically a subset of Σ*; each string from Σ* in L is called a sentence.
  • Formal language is denoted by L.
  • A formal language (L) can be either finite or infinite.
• Formal languages are defined by a set of sentences (strings) over some alphabet where the legal strings comprise the sentences
• Formal languages are defined by a grammar including the syntax of the language
• Syntax refers to the structure or form of a language
• Semantics refers to the meaning of a language
• There are both finite and infinite languages
• The most interesting languages are infinite

Progressive Validity Examples

• Lexically valid means the words are valid.
• Syntactically valid means the sentence structure is valid.
• Semantically valid means the sentence makes sense.
• In natural language: "Augustine is a saint" is lexically, syntactically, and semantically valid.

Regular expressions

• A concise and formal method for describing languages is needed because languages can be infinite.
• A regular expression (r) is a pattern, represented as a string, that concisely and formally denotes the strings of a language.
  • The regular expression (r) itself is a string in a language termed the metalanguage, utilized to describe another language with its own alphabet and syntax
• Lexemes can be formally described by regular grammars.
  • '+' describes "or".
  • '*' denotes "0 or more occurrences of the previous character".
  • '()' denotes "precedence among strings".
  • Examples:
    • opus* results in {opu, opus, opuss, opusss, ...}
    • (ab)* results in {ɛ, ab, abab, ababab, ...}
    • opus(1+2+3+4+5+6+7+8+9) results in {opus1, opus2, opus6, ...}
    • opus(1+2+3+4+5+6+7+8+9)(0+1+2+3+4+5+6+7+8+9)* results in {opus1, opus2, ..., opus10, ..., opus21, ..., opus99}

Finite-State Automata

• Elements of a set of sentences enumerate a formal language extensionally
• Denoting the set of sentences of languages defines a regular language intensionally with a regular expression
• A finite-state automaton (FSA) recognizes whether a string is a sentence (legal string denoted by regular expressions) in a particular language
• Deciding whether a string is a sentence in a particular language is a simplified computational mechanism that can be thought of as an automaton

Regular Languages

• Regular grammars define or generate regular languages and are also called linear grammars
• Any finite language is regular, but the reverse is not true
  • The finite language {a, b, c} is denoted by the regular expression a+b+c
• Sentences from regular languages are recognized using finite state automata (FSA)

Grammars and Backus-Naur Form (BNF)

• Grammars define languages like the regular expression and is also a Metalanguage like regular expressions.
• A grammar has its own syntax, different from the language it defines.
• A metalanguage defines grammar called Backus-Naur Form (BNF).
  • Named after John Backus and Peter Naur, who respectively developed and extended the notation for ALGOL 58 (1958) and ALGOL 60 (1960)
• A formal grammar can be used to define a formal language.
• A formal grammar example defined in BNF representing the language denoted by the a* regular expression is:
  • S → a S
  • S → ε

Grammar Formal Definition

• The formal definition of a grammar is G = (V, Σ, P, S)
  • V is a set of non-terminal symbols, like {S}.
  • Σ is an alphabet, where Σ = {a}.
  • P is a finite set of production rules, of the form x → y, where x and y are strings over Σ ∪ V and x ≠ €.
  • S is the start symbol such that S ∈ V.
• V represents the set of non-terminal alphabet, while ∑ is set of terminal alphabet and V ∩ Σ = Ø
• Formally, for each terminal symbol t, t ∈ Σ* (Σ set of all strings over Σ)
  • Strings of symbols from ∑ are called terminals.
  • Terminals are the atomic lexical units of a program commonly called lexemes (identifiers in programming languages).
• G = ({S}, {a}, {S → aS, S → ε}, S) is an example of a formal declaration of a language grammar with BNF (see prev. slides)

Grammar As Generative Device

• A stream of tokens must conform to a Grammar and must be arranged in a particular order

• Grammars define how sentences are constructed

• Sentences from the language it defines are generated when applying the production rules starting with the start symbol

• An example of a derivation of the sentence aaaa in a given language illustrates:

  S ⇒ aS ⇒ aaS ⇒ aaaS ⇒ aaaaS ⇒ aaaa

• Tokens must adhere to a Grammar and possess a certain order.

• Grammars specify how sentences get constructed. Beginning with the start symbol, generate a sentence to define the language. For G (V, Σ, P, S),

  • The language generated by G is represented as L(G) = {x | x ∈ Σ* and s * x}
  • * means finally derives

• A grammar in BNF for language denoted by regular expression opur*

  • (V={S,W}, Σ={o, p, u, r}, P= {S → opuW, W → rW, W → ε}, {S})

Chompsky Hierarchy

• Linguist Noam Chomsky formulated a set of grammars used to describe language syntax in the late 1950s, called as Chomsky hierarchy. The hierarchy consists of the following
  • Level 1: Regular Grammar
    • Regular Grammar use includes lexeme descriptions of programming languages
    • C Keywords
    • Complete sets of lexemes in a language are referred to as a lexicon
  • Level 2: Context-Free Grammar
  • Level 3: Context-Sensitive Grammar

Regular Grammar (Type 1)

• A grammar is regular if and only if every production rule is in one of the following two forms:

  X → zY
  X → z where X ∈ V, Y ∈ V, and z∈ Σ*

• Grammars conforming to these patterns are also called right-linear grammars

• Grammars whose production rules follow the pattern X → Yz and X → z are called left-linear grammars:

• Right-linear and Left-linear grammars generate regular languages

• Regular grammars are referred to as linear grammars.

Regular Grammar and Regular Language

• Regular grammars define regular languages.
• A regular gamma is a generative device for a regular languages, where it generates sentences from the regular languages that it defines
  • A grammar does not have to be regular to generate a regular language
• Non regular grammars can generate a regular language

Finite-State Automota / Regular Expressions

• Regular expressions, regular grammars, and finite-state automata are equivalent in their power to denote, generate, and recognize regular languages.
• No regular language could be denoted with a regular expression that could not be decided by a FSA or generated by a regular grammar
• An enumeration of the elements of a set of sentences defines a regular language extensionally, while a regular expression, finite-state automata, and regular grammar each define a regular language intensionally.

Regular Grammar Limitations

• Regular grammars cannot express language syntactic structures that nest arbitrarily, including:

  • Balanced pairs of lexemes "{}"
  • Checking palindromes
  • Begin/End keyword pairs
  • Parentheses in mathematical expressions

• Expressions are expressive enough to denote lexemes, but not the programming languages' higher-order syntactic structures

Context Free Grammars

• Context-free grammar (CFG): a grammar is a context-free grammar if and only if every production rule is in the following form:

  X → Y where X ∈ V and Y ∈ (Σ ∪ V)*

• There is only one non-terminal on the left-hand side of any context-free grammar rule, can be replaced anywhere.

• Less restrictive form can be found in the right-hand rule. CFGs are less restrictive than regular grammars

• Context-free grammars define a class of formal languages called context-free languages.

Regular Grammar vs Context Free Grammar

• Balanced pairs of syntactic entities is the essence of a Dyck language and is at the heart of context-free languages.
• The ability to express balanced pairs and a single syntactic feature is the essence of a context-free grammars
• Regular grammar is context-free grammar, but the reverse is not correct

Language Generation: Sentence Derivations

• Given a set of context free grammars an English vocabulary set of
  • →
    .
  • → a
  • → an
  • → the
  • → apple
  • → rose
  • → umbrella
  • → is
  • → appears
  • → here
  • and → there
    • Non terminals include the basic parts of speech. Terminals include common English words.
    • Grammar is the set of production rules and starting symbol is
• Language is generated by conforming to top-down construction using grammar, creating a construct derivation. For example the sentence "the apple is there" is derived as follows.
  • ⇒
    .
  • there.
  • is there.
  • apple is there.
  • the apple is there.
• The grammar above uses the vertical bar | indicating the "alternation symbol" when the rules are in "Extended version of BNF"

Parsing

• Grammar can be one of two devices
  • Generative: grammar >- sentence
  • Recognition: sentence >- grammar
• Parsing is for recognition. Parsers do the reverse operation starting with the sentence and conforming to a grammar
  • The production rules of a grammar move forward
  • The derivation rules of a grammar move backwards
• Parsing proceeds from left-to-right
  • The dot . indicates progress
  • The left of the . is considered the "stack"
  • The right of the . is the "handle"

Shift Reduce or Bottom-Up Parsing

• Shift-reduce, also known as "bottom up parsing" starts with terminals and is reduced back to the start signal
• It constructs a rightmost derivation in reverse using the terminals

Parsing Examples

• Bottom up parsing takes the general form

  .x + y*z

  x. + y*z

  id . + y * z

  expr . + y*z

  expr + . y * z

  expr + y. * z

  expr + id . * z

  expr + expr . * z

• Two types of conflicts arise at the "shift" in

  + .* z -Shift action * -Reduce action +

Shift Reduce conflict

• A shift reduce results from having two different choices during reduction
  • Shift for * gives multiplication precedence "desireable outcome"
  • Reduce gives addition precedence "undesirable outcome"
• These parse processes deal with syntax over semantics

Reduce Reduce Conflicts

• A reduce-reduce conflict will result in multiple parse trees that represent the syntax
• Formal grammars define syntax only
• BNF grammars define both syntax and semantics

Parse Trees

• An ambiguous grammar is the underlying source of shift-reduce and reduce-reduce conflicts.
• Ambigious grammars occurs if parsing is possible in one way.
  • The parse tree for a sentence is a graphical representation of its derivation.
    • Rooted at starting symbol.
    • Non-leaf vertices/nodes are non-terminals. Leaves are terminals. Trees are fully expanded

Effect of Ambiguity Semantics

• The grammar must be ambiguous if a sentence from that language has more than one parse tree
• Last three rows of a table will show the grammar as ambiguous, last two will have interpretation problems
• Syntactic Ambiguity
  • Multiple syntactic structures
  • Example: They are moving pictures
• Semantical Ambiguity
  • Only one: syntactic structures
  • Multiples meanings
  • Example: The mouse correct on my computer

Effects Of Semantics

• Ambiguity in the context of independence and expressions such as precedence and / or associativity and the operations
• Ambiguity can occur with context dependence in English such language as syntactic ambiguity
  • Syntactic ambiguity leads to semantical ambiguity, consider "Time flies like an arrow" or "They are moving pictures"
• Semantical ambiguity can occur with context independence such polyseme languages with words including mouse, book, or flies
  • Consider "I see a mouse on top of the computer"
  • The mouse is the species or the computer
• Programming Languages are ambiguous like (Integer)-a

Interdependance of Types of Ambiguity

• Lexical, and semantic ambiguities exist, and are context dependent

Grammar Determination is Ambiguous

• Grammar is ambiguous as follows
  • Generate the expression from grammar
  • Give two syntax trees in the grammar for that expression
• Note that
  • Grammar comes from the grammar code expression;
  • Parse trees must have expression codes at the leaves
  • Parse trees cannot violate rules
  • Terminals are always trees

Disambiguating Grammar

• Two choices exists to resolve grammar issues
  • Create grammar documentation specifying operations ordering
    • Inherent grammatical ambiguity and ambiguation in English exist
  • Disambiguation

Grammar Resolution

• Syntax implies semantics and desideratum.
• Precedence
• Associativity
• Occurs lower in parse threes because of bottom up evaluation when discussing higher precedence.
• State a disabmiguating rule such as order of precedence. Most languages provide an inherent order for addition and multiplication but other languages including APL don't
• Some grammar is inherently ambiguous with the rules and Context Free Grammars can resolve
• To resolve, grammar can be revised
• Not always possible
• Some are inherently ambiguous in context free

Operator Resolution

Introduce new steps
    -  Implement an operation within existing structure, will always be lower than edits in the tree"Work out solution for x + y ∗ z

• Express ::=Express + Term
• Express ::=Express − Term
• Express ::=Term
• Term ::=Term ∗ Factor
• Term ::=Term / Factor
• Factor ::= (Express)
• Factor::= Number
• Yes, is the term till ambiguous? Yes.Why? What about associativity problems？How can we disambiguate it？。

Associates Of Operators

• Associativity

  • Use same precedence in the operator when handling
    • (6-3)-2 = 1 is left associative
    • • (-(-6))) = -6 is a right associative
  • Addition + for floating point operations.
  • C is a right associative

  Overcoming ambiguity of association;

  -Right recursive rules lead to right association; 。
  

Dangling ELSE

• When curly braces are not present and are not used for disimbiguation, if statements can cause ambiguity errors

  if exprl

  if expr2

  • To which does else associate with

  if (if b 3) x −4；else y - 5

Source : is from ambiguous grammar.if condstmt or if cond stmt, then else state occurs

Parse tree of the conditional can illustrate ambiguity during (if) state, or (else) state.

For example, two derivations of the number 132:

Ambiguous Grammar

• The grammar must be ambiguous if a sentence from that language has more than one parse tree

Derivations of 132

• LeftMost derivation:

  ⇒

               ⇒ <number>  <digit>
  
             ⇒  <number><digit> <digit>
  
               ⇒ <digit><digit><digit>
  
                   ⇒  1 <digit><digit>
  
                      ⇒ 13 <digit>
  
                          ⇒ 132
  

• Right Most Derivation

  ⇒

         ⇒ <number><digit>
  
         ⇒ <number> 2 \
        ⇒<number><digit>2
  
        ⇒ number 32
  
         ⇒ d322
  
        ⇒ 132
  

The two parse trees for the expression "x"

• If the same expression produces multiple syntactic derivations it's said to have the syntactive ambiguation.

Types of Grammar

• Context free grammar - Cannot represent count. By definition

  +Context sensitive or not context free . Ex Capitalization of initial number. S starts with <startarticle

Context Sensitive Grammar:

• In context free grammar, the left-hand side of the production rule is not limited to one

• is the second production provides context

• only applies in context of

The Chomsky Hierarchy

• Type 3 regular language
• Regular grammar
• Deterministic finite automaton
• X = zY
• X = Z
• Type2 context-free language
• Context-free grammar
• Pushdown automaton X
• Gamma
• Type 1 context-sensitive language
• Context-free grammar
• Linear bounded automaton
• Alpha - beta greater Aybeta. 1

Takeaways

• Identifiers and numerals can be described in programming in languages languages by regular.
• Nested experiences in program languages can be described in contact numbers.
• Neither is regular not a context free grammar can describe the data of a variables that must be.
• Grammas are language recognition devices.
• An ambiguous grammar poses a problem a language recognition too par trees of our language prove.
• Semantic properties including precedence and associativity can in a grammar.

This lesson defines language structure and semantics. It also explain metacharacters used in regular expressions like *, +, and ( ). Regular expressions are patterns that describe strings of a language.