jlj;l

ufeff14. Especificación de analizadores sintácticos LR
1. Conceptos básicos de análisis sintáctico:
YACC.py es usado para analizar la sintaxis del lenguaje. La sintaxis se especifica normalmente en términos de una gramática BNF (Gramática Libre de Contexto). Por ejemplo, para analizar simples expresiones aritméticas, lo primero que se debe hacer es escribir una gramática no ambigua, como porejemplo:
expression : expression + term
| expression - term
| term

term : term * factor
| term / factor
| factor

factor : NUMBER
| ( expression )

En esta gramática, los símbolos como NUMBER, +, -, * y / son conocidos como símbolos terminales y corresponden con los tokens de entrada.

Identificadores como TERM yFACTOR, refieren a reglas gramaticales compuestas de una colección de terminales y otras reglas, y estos son conocidos como no terminales.

El comportamiento de la semántica de un lenguaje se especifica usando una técnica conocida como “traducción directa de la sintaxis”. En esta técnica, los atributos están asociados a cada símbolo de una regla gramatical dada, junto con una acción. Cada vez que unaregla gramatical particular es reconocida, la acción describe que hacer. Por ejemplo, dada la expresión gramatical anterior, se podría escribir la especificación de una simple calculadora de la siguiente manera:

Grammar : Action

expression0 : expression1 + expression0.val term = expression1.val + term.val
|expression1 - expression0.val term = expression1.val - term.val|expression0.val term = term.val

term0: term1 * Factor term0.val = term1.val * Factor.val
|term1 / Factor term0.val = term1.val / Factor.val
|Factor term0.val = Factor.val

Factor: NUMBER factor.val = int(NUMBER.lexval)
|( expression ) factor.val = expression.val

Una buena manera de pensaracerca de esta técnica es ver a cada símbolo de la gramática como un tipo de objeto, asociando a cada símbolo un valor representando asi “estado”, es decir, asignarle un valor a los atributos. Por lo tanto las acciones semánticas son expresadas como una colección de funciones o métodos que operan sobre los símbolos y los valores asociados.
YACC usa una técnica de análisis conocida como LR-parsing.2. Yacc
2.1 Un ejemplo
Suponiendo que queremos hacer una gramática para una simple expresión aritmética como la que describimos anteriormente, a continuación se expondrá una manera de hacerlo con yacc.py:

# Yacc example

import ply.yacc as yacc

# Get the token map from the lexer. This is required.
from calclex import tokens

def p_expression_plus(p):
expression : expressionPLUS term'
p[0] = p[1] + p[3]

def p_expression_minus(p):
'expression : expression MINUS term'
p[0] = p[1] - p[3]

def p_expression_term(p):
'expression : term'
p[0] = p[1]

def p_term_times(p):
'term : term TIMES factor'
p[0] = p[1] * p[3]

def p_term_div(p):
'term : term DIVIDE factor'
p[0] = p[1] / p[3]

def p_term_factor(p):
'term :factor'
p[0] = p[1]

def p_factor_num(p):
'factor : NUMBER'
p[0] = p[1]

def p_factor_expr(p):
'factor : LPAREN expression RPAREN'
p[0] = p[2]

# Error rule for syntax errors
def p_error(p):
print "Syntax error in input!"

# Build the parser
parser = yacc.yacc()

while True:
try:
s = raw_input('calc > ')
except EOFError:
break
ifnot s: continue
result = parser.parse(s)
print result

Cada función acepta un argumento “p” que es una secuencia que contiene valores de cada símbolo gramatical con su regla correspondiente.

Los valores son mapeados a símbolos gramaticales de la siguiente manera:

def p_expression_plus(p):
'expression : expression PLUS term'
# ^ ^ ^...