¿Cómo puedo incorporar operadores ternarios en un algoritmo de escalada de precedencia?

parsing expression

Question

Seguí la explicación dada en la sección "Ascenso de precedencia" en esta página web para implementar un evaluador aritmético utilizando el algoritmo de ascenso de precedencia con varios prefijos unarios y operadores de infijo binario. También me gustaría incluir operadores ternarios (a saber, el operador condicional ternario ?: :).

El algoritmo dado en la página web utiliza la siguiente gramática:

E --> Exp(0) 
Exp(p) --> P {B Exp(q)} 
P --> U Exp(q) | "(" E ")" | v
B --> "+" | "-"  | "*" |"/" | "^" | "||" | "&&" | "="
U --> "-"

¿Cómo puedo incorporar operadores ternarios en esta gramática?

Answer 1

Defina los dos puntos para tener una prioridad más baja que el signo de interrogación. En otras palabras, un? b: c se analizaría como (a? b): c. Esto permite al analizador construir un nodo de sintaxis abstracta (si / entonces / vacío-si no), que luego sería operado por el operador ":" para proporcionar el otro componente deseado.

Las relaciones de precedencia también preservan la composabilidad del operador. Por ejemplo, un? antes de Cristo ? d: e se analiza como (a? b): (c? d): e, como cabría esperar.

Espero que esto ayude.

Answer 2

Me he encontrado con esta pregunta en busca de información sobre la transformación de operadores ternarios a Invertir las Notaciones Polacas (RPN), por lo que aunque no tengo una implementación sólida para implementar el operador ?: Con Precedence Climbing, creo que puedo dar Alguna pista para transformar el operador ?: en RPN usando dos pilas ... que es similar al algoritmo de Shunting Yard en la página web que has dado.

(Editar) Tengo que señalar que lo que estoy haciendo aquí no es muy eficiente (deben evaluarse ambas ramas del operador ternario), pero demostrar lo fácil que es incorporar un nuevo operador ( ?: En un marco existente (el código de transformación RPN) (declarando ? y : con los dos niveles de precedencia más bajos).

Quiero comenzar con algunos ejemplos de cómo las expresiones con ?: Se transforman a RPN en función de mi analizador ... Estoy agregando dos operadores en lugar de uno, el ? y : pero no creo que haga una gran diferencia ya que : y ? siempre se juntarán (es más conveniente que el RPN y la expresión original tengan el mismo número de tokens). En los ejemplos puedes ver cómo funciona.

Ejemplo 1: 1 + ((0+1) ? 2 : 3 + 8) + 4

RPN: 1 0 1 + 2 3 8 + ? + 4 +

Ahora evaluemos el RPN.

1 - Empujando los primeros elementos en la pila y nos encontramos con el primer operador binario:

1 0 1 y operador + , agregamos los 2 elementos principales, convirtiendo la pila en 1 1

2 - Luego, presionando tres elementos más y nos encontramos con el segundo operador binario:

1 1 2 3 8 + ------> 1 1 2 11

3 - Ahora tenemos : y ? . Esto realmente nos dice que seleccionemos la rama consecuente (el segundo elemento superior en la parte superior de la pila, 2 ) o la rama alternativa (el elemento superior en la pila, 11 ), basado en el predicado (el tercer elemento superior en la pila , 1 ). Como el predicado es 1 (verdadero), elegimos 2 y descartamos 11. El analizador muestra los 3 elementos (predicado / consecuente / alternativo) y retira el elegido (en este caso, la rama consecuente), por lo que la pila se convierte en

1 2

4 - Consumir los elementos restantes:

1 2 + ------> 3

3 4 + ------> 7

Ejemplo 2: 1 + ((0+0+0?0:0) ? 2 : (3 + 8)) + 4

RPN: 1 0 0 + 0 + 0 0 ? 2 3 8 + ? + 4 +

Evaluación:

Comienzo:

1 0 0 + 0 + 0 0 ? 2 3 8 + ? + 4 +

Después de agregar 0 a 0:

1 0 0 + 0 0 ? 2 3 8 + ? + 4 +

Después de agregar 0 a 0:

1 0 0 0 ? 2 3 8 + ? + 4 +

Después de la primera :? elige 0 :

1 0 2 3 8 + ? + 4 +

Después de agregar 3 y 8:

1 0 2 11 ? + 4 +

Después del ?: Elige 11:

1 11 + 4 +

Después de agregar 1 y 11:

12 4 +

Finalmente:

16

Esto puede sugerir que es posible transformar una expresión con ?: notación de pulido inverso. Como la página web dice que RPN y AST son equivalentes, ya que podrían transformarse entre sí, el operador ternario debería poder implementarse con Precedence Climbing de manera similar.

Una cosa que debe hacerse parece ser la "prioridad" (o precedencia) del operador ?: Y realmente lo he encontrado al intentar la transformación RPN. He dado signos de interrogación y dos puntos la prioridad más baja:

Como puede ver en el ejemplo anterior, cuando estamos a punto de ejecutar ?: , La rama de precedencia y la rama alternativa y el predicado ya deberían haber sido evaluados, dando como resultado un solo número. Esto está garantizado por la precedencia.

A continuación se muestra la tabla de prioridad (prioridad).

! ~ > * / % > + - > & > ^ > | > && > || > ? > :

El ? y : son de la menor prioridad, es decir, en expresiones como 1? 2 + 3: 4 + 5 ? y : nunca tomará los operandos a su alrededor.

? precede : para hacer : aparecer antes ? en el RPN. A mi entender, esto es solo una opción de diseño porque : y ? Ni siquiera necesariamente tienen que dividirse en 2 operadores en primer lugar.

Espero que esto ayude..

Referencia: http://en.cppreference.com/w/cpp/language/operator_precedence

Answer 3

Para ser específico, usaré C / C ++ / Java''s ?: Como ejemplo.

Parece que en esos idiomas el operador ?: Permite cualquier expresión válida entre ? y : incluidas las expresiones formadas con ?: sí mismo y las formadas con operadores, cuya prioridad es inferior a la precedencia de ?: , eg = y , (ejemplos: a ? b = c : d , a ? b , c : d , a ? b ? c : d : e ).

Esto sugiere que deberías tratar ? y : exactamente de la misma manera que ( y ) al analizar expresiones. ¿Cuándo has analizado ? expr : ? expr : en conjunto, es un operador binario. Entonces, usted analiza ( expr ) y ? expr : ? expr : de la misma manera, pero la primera es una expresión, mientras que la última es un operador binario (con una expresión incrustada en ella).

Ahora que ? expr : es un operador binario ( a ?-expr-: b no es diferente de a * b en términos de "binario"), debería ser capaz de admitirlo como cualquier otro operador binario que ya sea compatible.

Personalmente, no me tomaría la molestia de dividirme ?: en operadores binarios separados propios. Al final, sigue siendo un operador ternario y debe estar vinculado a 3 operandos y considerarse como un todo durante la evaluación de la expresión. Si está siguiendo el enfoque en el artículo que mencionó en la pregunta y está creando un AST, entonces tiene que ir, ?: Tiene un nodo secundario izquierdo, un nodo secundario derecho (como cualquier otro operador binario) y, además, un nodo hijo medio.

La precedencia de ?-expr-: en conjunto debe ser baja. Sin embargo, en C / C ++ (y en Java?) No es el más bajo. Depende de usted decidir lo que quiere que sea.

Hasta ahora no hemos cubierto la asociatividad de ?: . En C / C ++ y Java ?-expr-: es asociativo a la derecha al igual que el operador de asignación = . Una vez más, depende de usted hacer que sea asociativo por la izquierda o mantenerlo asociativamente por la derecha.

Y esto:

E --> P {B P}
P --> v | "(" E ")" | U P
B --> "+" | "-" | "*" | "/" | "^"
U --> "-"

Debería convertirse en algo como esto:

E --> P {B P}
P --> v | "(" E ")" | U P
B --> "+" | "-" | "*" | "/" | "^" | "?" E ":"
U --> "-"