En un analizador LR (0), cada estado consta de una colección de elementos LR (0), que son producciones anotadas con una posición. En un analizador LR (1), cada estado consta de una colección de elementos LR (1), que son producciones anotadas con una posición y un carácter anticipado.
Se sabe que dado un estado en un autómata LR (1), el conjunto de configuración formado al soltar las fichas anticipadas de cada elemento LR (1) produce un conjunto de configuración correspondiente a algún estado en el autómata LR (0). En ese sentido, la principal diferencia entre un autómata LR (1) y un autómata LR (0) es que el autómata LR (1) tiene más copias de los estados en el autómata LR (0), cada uno de los cuales está anotado con anticipación información. Por esta razón, los autómatas LR (1) para un CFG dado son típicamente más grandes que el analizador LR (0) correspondiente para ese CFG.
Mi pregunta es cuánto más grande puede ser el autómata LR (1). Si hay símbolos terminales distintos en el alfabeto de la gramática, entonces, en principio, podríamos necesitar replicar cada estado en el autómata LR (0) al menos una vez por subconjunto de esos símbolos terminales distintos, lo que podría conducir a un LR (1 ) autómata que es veces más grande que el autómata LR (0) original. Dado que cada elemento individual en el autómata LR (0) consiste en un conjunto de elementos LR (0) diferentes, podemos obtener una explosión aún mayor.n 2 n
Dicho esto, parece que no puedo encontrar una manera de construir una familia de gramáticas para las cuales el autómata LR (1) sea significativamente más grande que el autómata LR (0) correspondiente. Todo lo que he probado ha llevado a un aumento modesto de tamaño (generalmente alrededor de 2-4x), pero parece que no puedo encontrar un patrón que conduzca a una gran explosión.
¿Existen familias conocidas de gramáticas libres de contexto cuyos autómatas LR (1) son exponencialmente más grandes que los autómatas LR (0) correspondientes? ¿O se sabe que, en el peor de los casos, no se puede obtener una explosión exponencial?
¡Gracias!
fuente
Respuestas:
La gramática
tiene el estado LR (0) expandido a variantes en el autómata LR (1) ya que todas las particiones de son posibles cabeza que aparece en diferentes contextos. El número de estados en el LR (0) autómata por otro lado es lineal en términos de . Por lo tanto un factor de expansión del orden de es posible.
Editar:
tendré que verificar más tarde cuando tenga más tiempo, creo que agregar daría el factor exponencial en casi todos los estados LR (0).Tnorte→ T0 0 Eso da como resultado un conflicto de reducción de turnos.fuente
Tales límites inferiores a veces son difíciles de construir y pueden evocar una teoría CS más profunda (por ejemplo, en casos, separaciones de clases de complejidad). Este artículo parece dar una construcción teórica / límites inferiores que busca, por ejemplo, en el Teorema 5, que pone un límite inferior en los símbolos totales y, por lo tanto, también establece. Las referencias también incluyen otras construcciones similares / límites inferiores.
Sobre el tamaño de analizadores y LR (k) -grammars / Leunga, Wotschkeb
fuente