¿Es esta una gramática ambigua? ¿Cómo debería resolverlo?

Question

Para comenzar esto, mi conocimiento de este tipo de cosas es insignificante.

De todos modos, he estado desarrollando una gramática sin contexto para describir la estructura de las expresiones alegbraicas, así puedo aprender cómo funciona el algoritmo de análisis CYK. Entiendo cómo una estructura de este tipo puede funcionar con expresiones infrecuentes algebraicas, pero no puedo entender cómo desarrollar una gramática que pueda manejar las definiciones unarias y binarias del operador "-".

Como referencia, aquí está la gramática que he escrito (donde S es el símbolo inicial) en CNF:

S -> x
A -> OS
S -> LB
B -> SR
S -> KS
O -> +
O -> -
O -> *
O ->/
O ->^
K -> -
L -> (
R ->)

El problema es que ¿cómo puede el CYK analizar algoritmo de saber de antemano si se debe decidir entre S -> KS y A -> OS cuando se encuentra con el operador "-" ¿Ya es una gramática libre de contexto? Y lo más importante, dado que los lenguajes de programación pueden manejar los lenguajes con el signo menos binario y unario, ¿cómo debería analizar esto de manera razonable?

Answer 1

Este parece ser un problema relacionado con autómatas de estados finitos y no me acuerdo de todo, desde mi curso, pero me escribió un analizador CYK en OCaml , así que voy a seguir adelante y tomar un tiro :)

Si usted está tratando de analizar una expresión como 3- -4 por ejemplo, usted tendría su regla S -> K S consumir el -4 y luego la regla A -> O S absorbería la - -4. Eventualmente, esto funcionaría hasta la regla de producción S más alta. Sin embargo, debes tener cuidado con la gramática que estás utilizando, ya que la regla de producción A que enumeró no puede ser contactada desde S y probablemente deberías tener una regla de S -> S O S de algún tipo.

La forma en que funcionan los algoritmos de análisis CYK es retrocediendo, no a través del "conocimiento previo" que mencionaste en tu pregunta. Lo que su algoritmo CYK debería hacer es analizar el -4 como una regla S -> K S y luego trataría de absorber el segundo - con la regla S -> K S nuevamente porque esta regla de producción permite una cadena larga arbitrariamente -. Pero una vez que su algoritmo se da cuenta de que está atascado con el análisis intermedio 3 S, se da cuenta de que no tiene símbolos de producción que pueda usar para analizar esto. Una vez que se da cuenta de que esto ya no se puede analizar, se volverá y en su lugar intentará analizar el - como una regla y continuar de forma feliz.

Esto significa que su gramática permanece libre de contexto ya que una gramática sensible al contexto significa que tiene terminales en el lado izquierdo de las reglas de producción, por lo que es bueno en ese sentido. HTH!

Answer 2

La gramática es ambigua, y el analizador no puede decidir qué caso tomar.

probablemente debería usar una gramática como la siguiente:

S -> EXPR 
EXPR -> (EXPR) 
EXPR -> - EXPR 
EXPR -> EXPR + EXPR 
EXPR -> EXPR - EXPR 
// etc... 

Answer 3

Las gramáticas basadas en expresiones algebraicas son bastante difíciles de desambiguar. Estos son algunos ejemplos de problemas que deben abordarse:

a + b + c crea naturalmente dos árboles de análisis sintáctico. Para resolver esto, debe resolver la ambigüedad de la asociatividad de +. Es posible que desee dejar que una estrategia de análisis de izquierda a derecha se encargue de esto, pero tenga cuidado: la exponenciación probablemente se asocie de derecha a izquierda.

a + b * c crea naturalmente dos árboles de análisis sintáctico. Para solucionar este problema, debe lidiar con la precedencia del operador.

multiplicación implícita (a + bc), si está permitido, crea todo tipo de pesadillas, principalmente en tokenización.

resta unaria es problemático, como usted menciona.

Si queremos resolver estos problemas, pero todavía tenemos una gramática de análisis rápido especializada en álgebra, un enfoque es tener varios "niveles" de EXPR, uno para cada nivel de enlace requerido por niveles de precedencia. Por ejemplo,

TERM -> (S) 
EXPO -> TERM^EXPO 
PROD -> PROD * EXPO 
PROD -> PROD/EXPO 
PROD -> -PROD 
SUM -> SUM + PROD 
SUM -> SUM - PROD 
S -> SUM 

Esto requiere que también permite que la "promoción" de tipos: SUM -> PROD, PROD -> CAD, CAD -> PLAZO, etc, por lo que las cosas pueden terminar.

Espero que esto ayude!