PDF de programación - Compiladores: compilación de expresiones regulares

Compiladores: compilación de expresiones regulares - (c)2014 LSUB

1/25/16, 2:48 PM

Compiladores: compilación de
expresiones regulares

Francisco J Ballesteros
LSUB, URJC

http://127.0.0.1:3999/s05.regexp.slide#1

Page 1 of 58

Compiladores: compilación de expresiones regulares - (c)2014 LSUB

1/25/16, 2:48 PM

Expresiones regulares

En este tema vamos a

definir expresiones regulares sencillas

implementar un compilador predictivo para las mismas

implementar un intérprete que las ejecute

Normalmente mejor hacerlo como lo hizo Ken Thompson

Ken regexps by Russ Cox (http://swtch.com/~rsc/regexp/regexp1.html)

Nosotros vamos a hacerlo paso a paso

http://127.0.0.1:3999/s05.regexp.slide#1

Page 2 of 58

Compiladores: compilación de expresiones regulares - (c)2014 LSUB

1/25/16, 2:48 PM

Expresiones regulares

Para nuestros propósitos, una regexp será:

Cualquier runa sin significado especial, r

encaja con ella misma

La runa .

encaja con cualquier runa

Dos expresiones a y b concatenadas ab

encajan si un prefijo encaja con a y el sufijo con b

La expresión a|b

encaja si encaja a o encaja b

http://127.0.0.1:3999/s05.regexp.slide#1

Page 3 of 58

Compiladores: compilación de expresiones regulares - (c)2014 LSUB

1/25/16, 2:48 PM

Expresiones regulares

La expresión a*

o el string vacío, o encaja como a, o como aa, ...

La expresión (a)

encaja igual que la expresión a

La expresión \r

encaja con la runa r

http://127.0.0.1:3999/s05.regexp.slide#1

Page 4 of 58

Compiladores: compilación de expresiones regulares - (c)2014 LSUB

1/25/16, 2:48 PM

Gramática

Podríamos utilizar esta gramática:

RE ::= TERM OPTS
OPTS ::= '|' TERM OPTS | <empty>
TERM ::= ATOM ATOMS
ATOMS ::= ATOM ATOMS | <empty>
ATOM ::= rune STAR | '(' RE ')' STAR
STAR ::= '*' | <empty>

Vamos a hacer que el scanner se ocupe de los
escapes de runas especiales

La gramática fuerza a precedencia de los operadores

http://127.0.0.1:3999/s05.regexp.slide#1

Page 5 of 58

Compiladores: compilación de expresiones regulares - (c)2014 LSUB

1/25/16, 2:48 PM

Lex

Utilizaremos rune como token.

type lex struct {
txt []rune
Debug bool
}

type Lexer interface {
// return next token
Scan() (rune, error)
// Look ahead one token
Peek() (rune, error)
}

func NewLex(s string) *lex {
return &lex{txt: []rune(s)}
}

http://127.0.0.1:3999/s05.regexp.slide#1

Page 6 of 58

Compiladores: compilación de expresiones regulares - (c)2014 LSUB

1/25/16, 2:48 PM

Lex

Y marcamos las runas especiales

const (
runeop rune = 0x40000000
runeops = "|*.()"
Or = runeop | '|'
Star = runeop | '*'
Lpar = runeop | '('
Rpar = runeop | ')'
)

http://127.0.0.1:3999/s05.regexp.slide#1

Page 7 of 58

Compiladores: compilación de expresiones regulares - (c)2014 LSUB

1/25/16, 2:48 PM

Lex

func (l *lex) scan() (rune, error) {
if len(l.txt) == 0 {
return 0, io.EOF
}
r := l.txt[0]
l.txt = l.txt[1:]
if r == '\\' {
if len(l.txt) == 0 {
return 0, fmt.Errorf("unexpected EOF")
}
r := l.txt[0]
l.txt = l.txt[1:]
return r, nil
}
if strings.IndexRune(runeops, r) >= 0 {
r |= runeop
}
return r, nil
}

http://127.0.0.1:3999/s05.regexp.slide#1

Page 8 of 58

Compiladores: compilación de expresiones regulares - (c)2014 LSUB

1/25/16, 2:48 PM

Lex

func (l *lex) Peek() (rune, error) {
old := l.txt
r, err := l.scan()
l.txt = old
return r, err
}

func (l *lex) Scan() (rune, error) {
t, err := l.scan()
if l.Debug && err == nil {
isop := t&runeop != 0
x := t & ^runeop
if isop {
fmt.Printf("scan <%c>\n", x)
} else {
fmt.Printf("scan '%c'\n", x)
}
}
return t, err
}

http://127.0.0.1:3999/s05.regexp.slide#1

Page 9 of 58

Compiladores: compilación de expresiones regulares - (c)2014 LSUB

1/25/16, 2:48 PM

Lex

Y podemos probarlo...

func main() {
txt := `ab|c*\*\`

l := NewLex(txt)
l.Debug = true
for {
if _, err := l.Scan(); err != nil {
fmt.Printf("error %s\n", err)
break
}
}
}

Run

http://127.0.0.1:3999/s05.regexp.slide#1

Page 10 of 58

Compiladores: compilación de expresiones regulares - (c)2014 LSUB

1/25/16, 2:48 PM

Parsing

Este es el parser con depuración, pero sin hacer nada más.

type Rexp struct {
l *lex
Debug, Debuglex bool
lvl int
}

func (re *Rexp) trz(tag string) {
if re.Debug {
s := strings.Repeat(" ", re.lvl)
fmt.Printf("%s%s\n", s, tag)
}
re.lvl++
}

func (re *Rexp) untrz() {
re.lvl--
}

func NewRexp(s string) *Rexp {
return &Rexp{l: NewLex(s)}
}

http://127.0.0.1:3999/s05.regexp.slide#1

Page 11 of 58

Compiladores: compilación de expresiones regulares - (c)2014 LSUB

1/25/16, 2:48 PM

Parsing

func (re *Rexp) Parse() error {
re.l.Debug = re.Debuglex
return re.parseRe()
}

// RE ::= TERM OPTS
func (re *Rexp) parseRe() error {
re.trz("re")
defer re.untrz()
if err := re.parseTerm(); err != nil {
return err
}
return re.parseOpts()
}

http://127.0.0.1:3999/s05.regexp.slide#1

Page 12 of 58

Compiladores: compilación de expresiones regulares - (c)2014 LSUB

1/25/16, 2:48 PM

Parsing

// OPTS ::= '|' TERM OPTS | <empty>
func (re *Rexp) parseOpts() error {
_, _, found := re.match(Or)
if !found {
return nil
}
re.trz("opts")
defer re.untrz()
if err := re.parseTerm(); err != nil {
return err
}
return re.parseOpts()
}

// TERM ::= ATOM ATOMS
func (re *Rexp) parseTerm() error {
re.trz("term")
defer re.untrz()
if err := re.parseAtom(); err != nil {
return err
}
return re.parseAtoms()
}

http://127.0.0.1:3999/s05.regexp.slide#1

Page 13 of 58

Compiladores: compilación de expresiones regulares - (c)2014 LSUB

1/25/16, 2:48 PM

Parsing

// ATOMS ::= ATOM ATOMS | <empty>
func (re *Rexp) parseAtoms() error {
re.trz("atoms")
defer re.untrz()
if err := re.parseAtom(); err != nil {
if err == io.EOF || err == ErrNoAtom {
err = nil
}
return err
}
err := re.parseAtoms()
if err == io.EOF || err == ErrNoAtom {
err = nil
}
return err
}

http://127.0.0.1:3999/s05.regexp.slide#1

Page 14 of 58

Compiladores: compilación de expresiones regulares - (c)2014 LSUB

1/25/16, 2:48 PM

Parsing

// ATOM ::= rune STAR | '(' RE ')' STAR
func (re *Rexp) parseAtom() error {
r, err := re.l.Peek()
if err != nil { return err }
if r == Lpar {
re.trz("paren")
defer re.untrz()
re.l.Scan()
if err := re.parseRe(); err != nil {
return err
}
_, _, found := re.match(Rpar)
if !found { return ErrNoParen }
} else if r & runeop != 0 && r != Any {
return ErrNoAtom
} else {
re.trz(fmt.Sprintf("'%c'", r&^runeop))
defer re.untrz()
re.l.Scan()
}
return re.parseStar()
}

http://127.0.0.1:3999/s05.regexp.slide#1

Page 15 of 58

Compiladores: compilación de expresiones regulares - (c)2014 LSUB

1/25/16, 2:48 PM

Parsing

// STAR ::= '*' | <empty>
func (re *Rexp) parseStar() error {
_, _, found := re.match(Star)
if !found {
return nil
}
re.trz("star")
defer re.untrz()
return nil
}

http://127.0.0.1:3999/s05.regexp.slide#1

Page 16 of 58

Compiladores: compilación de expresiones regulares - (c)2014 LSUB

1/25/16, 2:48 PM

Parsing

Y ahora podemos ver el árbol sintáctico...

func main() {
txt := `ab|(c*\*\))\`
fmt.Printf("parsing '%s'\n", txt)
re := NewRexp(txt)
re.Debug = true
err := re.Parse()
fmt.Printf("sts %v\n", err)
}

Run

http://127.0.0.1:3999/s05.regexp.slide#1

Page 17 of 58

Compiladores: compilación de expresiones regulares - (c)2014 LSUB

1/25/16, 2:48 PM

¿Ahora qué?

Lo que queremos ahora es construir el AFND que
corresponde a la expresión regular.

El autómata lo interpretaremos luego para hacer matching

Hay que tener fresco cuál es el NFA para
una expresión regular

http://127.0.0.1:3999/s05.regexp.slide#1

Page 18 of 58

Compiladores: compilación de expresiones regulares - (c)2014 LSUB

1/25/16, 2:48 PM

Autómatas para expresiones regulares

NFA para

x

http://127.0.0.1:3999/s05.regexp.slide#1

Page 19 of 58

Compiladores: compilación de expresiones regulares - (c)2014 LSUB

1/25/16, 2:48 PM

Autómatas para expresiones regulares

NFA para

re1 re2

http://127.0.0.1:3999/s05.regexp.slide#1

Page 20 of 58

Compiladores: compilación de expresiones regulares - (c)2014 LSUB

1/25/16, 2:48 PM

Autómatas para expresiones regulares

NFA para

re1 | re2

http://127.0.0.1:3999/s05.regexp.slide#1

Page 21 of 58

Compiladores: compilación de expresiones regulares - (c)2014 LSUB

1/25/16, 2:48 PM

Autómatas para expresiones regulares

NFA para

re1 *

http://127.0.0.1:3999/s05.regexp.slide#1

Page 22 of 58

Compiladores: compilación de expresiones regulares - (c)2014 LSUB

1/25/16, 2:48 PM

NFA

type NFA struct {
op rune // operator at this state
last *NFA // last state in this NFA
on []rune // runes we transition on
to []*NFA // states we transition to

id int // debug
}

var nfanodes []*NFA

func NewNFA(op rune) *NFA {
n := &NFA{op: op, id: len(nfanodes)}
nfanodes = append(nfanodes, n)
return n
}

El NFA representa un estado y guarda las transiciones
Todos los estados los guardaremos en un array para luego

http://127.0.0.1:3999/s05.regexp.slide#1

Page 23 of 58

Compiladores: compilación de expresiones regulares - (c)2014 LSUB

1/25/16, 2:48 PM

NFA

Vamos a necesitar añadir una transición a un estado

func (n *NFA) trans(on rune, to *NFA) {
n.on = append(n.on, on)
n.to = append(n.to, to)
}

http://127.0.0.1:3999/s05.regexp.slide#1

Page 24 of 58

Compiladores: compilación de expresiones regulares - (c)2014 LSUB

1/25/16, 2:48 PM

Generación del