Definitionen Formale Sprachen

Ein Parse-Baum ist ein Baum für den gilt:

1. Es gibt 2 Arten von Knoten

a) Blätter sind Knoten ohne Kinder

b) Innere Knoten sind Knoten mit wenigstens 1 Kind

1. Blätter sind mit Variablen oder Terminal gekennzeichnet

2. Innere Knoten sind mit Variablen gelabeled

3. Gibt es Blätter mit einer Variable a, so existier eine Grammatik-Regel der Form:

   a -> ʎ,

4. Sind innere Knoten mit einer Variable a gelabled, so existiert eine Grammatik Regel der FOrm

   a -> x1 x2 x3 … xn

import ply.lex as lex

tokens = [ 'NUMBER', 'IDENTIFIER', 'ASSIGN' ]

def t_NUMBER(t):

r'0|[1-9][0-9]*(\.[0-9]+)?([eE][+-]?([1-9][0-9]*))?'

t.value = float(t.value)

return t

def t_IDENTIFIER(t):

r'[a-zA-Z][a-zA-Z0-9_]*'

return t

def t_ASSIGN_OP(t):

r':='

return t

literals = ['+', '-', '*', '/', '(', ')', ';']

t_ignore = ' \t'

def t_newline(t):

r'\n+'

t.lexer.lineno += t.value.count('\n')

def t_error(t):

c = t.value[0]

n = t.lexer.lexpos

l = t.lexer.lineno

print(f"Illegal character '{c}' at character number {n} in line {l}.")

t.lexer.skip(1)

lexer = lex.lex()

L ist kontext freie Sprache g.d.w. es eine CFG G gibt, das L = L(G) ist

Ein String ist eine endliche Abfolge von Zeichen aus Σ

Gegeben sei ein Alphabet Σ, dann ist L eine formale Sprache wenn L Teilmenge von Σ* und L ist präzise definiert.