lesson_01.md 2.1 KB

Formal languages and compilers

Luca Oddone Breveglieri

Introduction

What is a formal language?

Contrary to natural language, it is meant to communicate with machines.

A language is formal if its syntax (structure) and semantic (interpretation) are defined in a precise algorithmic way.

There is an effective procedure to verify the grammatical correctness of a phrase and determine its meaning.

It is a mathematical object composed by:
  • An alphabet and built over a
    • grammar consisting in axiomatic rules
    • or an automata

Hystorical notes

Years '50
  • Chomsky proposes the mathematical model of a grammar (1956)
Years '60
  • Connection between formal languages and automata
  • Invention of formal grammars
  • Development of automated compilation
Years '70-'80
  • Formal language theory becomes a standard university discipline
  • Introduction of SDKs like Flex or Bison

    Lesson 1

    Definition of a language

  • Alphabet: finite set of elements

  • String: Ordered set of atomic elements, possibly repeated

  • Language: Finite or infinite set of strings

Strings can be both finite or infinite.

The cardinality of a language determines the number of elements contained,

It can be 0 for the empty language or infinite for infinite languages.

Operations on strings

####Lenght of a string Is the number of elements contained $$|bbc|=3$$

####Equality of two strings Two strings are equal if and only if

  • They have the same length
  • Their elements coincide

Concatenation (product of strings)

  • Is a basic operation,
  • Is associative,
  • Changes the length.
Empty string (or null string) $\varepsilon$:

is the neutral element respective to concatenation

Substring:

Given a string x = u y v

  • x is a prefix
  • y is a substring
  • v is a suffix

if u,v ≠ Ɛ, y is a proper substring

Mirroring or Reflection

$x=atri$ $x^r=irta$

Repetition or iteration

The m-th power of a string concatenates the string to itself for m-1 times

$x= ab$ $x^n=\varepsilon$ $x^1=x=ab$ $x^2=(ab)^

Concatenation