Necessário para uma máquina de estado não determinística M = (Q, T, D, q 0 , F) construir uma máquina de estados finitos determinística M = (Q", T, D", q" 0 , F"). O estado inicial do autômato em construção é o ε-fechamento do estado inicial do autômato inicial. ε-fechamento - um conjunto de estados que são alcançáveis ​​a partir de um dado por transições ao longo de ε. Além disso, embora existam estados para os quais as transições não foram construídas (as transições são feitas por símbolos, as transições através dos quais estão no autômato original), para cada símbolo, o ε-fechamento do conjunto de estados que são alcançáveis ​​a partir do estado considerado por transição através do símbolo considerado é calculado. Se o estado que corresponde ao conjunto encontrado já existir, uma transição será adicionada a ele. Caso contrário, o novo estado recebido é adicionado.

Exemplo

Inicialização

Os estados correspondentes ao ε-fechamento do estado inicial são marcados. Esses estados corresponderão ao estado UMA futura CAD.

Primeira iteração

Existem transições do fechamento ε para os estados NCA 3 e 10 (de acordo com uma e c, respectivamente). Para o estado 3, o ε-fechamento é o conjunto de estados (3, 4, 6), para o estado 10 - (10). Vamos designar os novos estados DFA correspondentes a esses conjuntos como B e C.

Estado DKA	Conjunto de estados NFA
		uma	b	c
UMA	{1, 2, 9}	B	-	C
B	{3, 4, 6}	-	-	-
C	{10}	-	-	-

Segunda iteração

Do conjunto de estados do NFA (3, 4, 6) correspondente ao estado do DFA B existem duas transições - para o estado 5 (por b) e 7 (por c). Seus ε-closures se cruzam, mas os próprios conjuntos são diferentes, então eles recebem dois novos estados DFA - D e E. Dos estados do NFA correspondentes ao estado do DFA C, não há transições.

Estado DKA	Conjunto de estados NFA	Personagens saltáveis
		uma	b	c
UMA	{1, 2, 9}	B	-	C
B	{3, 4, 6}	-	D	E
C	{10}	-	-	-
D	{2, 5, 8, 9}	-	-	-
E	{2, 7, 8, 9}	-	-	-

Terceira iteração

Dos conjuntos de estados do NFA correspondentes aos estados do DFA D e E as transições são feitas para os conjuntos de estados correspondentes aos estados existentes (do conjunto (2, 5, 8, 9) correspondente ao estado D, sobre uma transição para o estado 3 pertencente ao conjunto (3, 4, 6) correspondente ao estado do DFA B, sobre c- transição para o estado 10 correspondente ao estado C; da mesma forma para o conjunto correspondente ao estado do DFA E). O processo de construção da tabela de estados e transições do DFA está concluído.

Estado DKA	Conjunto de estados NFA	Personagens saltáveis
		uma	b	c
UMA	{1, 2, 9}	B	-	C
B	{3, 4, 6}	-	D	E
C	{10}	-	-	-
D	{2, 5, 8, 9}	B	-	C
E	{2, 7, 8, 9}	B	-	C

Resultado:

Construindo uma gramática linear à direita a partir de um autômato finito

Cada estado está associado a um não-terminal. Se houver uma transição de estado X em um estado S sobre uma, adicione a regra X → aY. Para estados finais, adicione regras X→ e. Para transições ε - X → S.

Exemplo 1 (máquina de estado determinística)

• A → uma b | c C
• B → b D | c E
• C → e
• D → uma b | c C
• E → uma b | c C

Exemplo 2 (máquina de estado não determinística)

• 1 → 2 | 9
• 2 → uma 3
• 3 → 4 | 6
• 4 → b 5
• 5 → 8
• 6 → c 7
• 7 → 8
• 8 → 2 | 9
• 9 → c 10
• 10 → ε

Construção do DFA por RV

Vamos ter uma expressão regular r. Com base nesta expressão regular, é necessário construir um autômato finito determinístico D de tal modo que eu(D) = eu(r).

Modificação de expressão regular

Vamos adicionar um símbolo a ele, significando o final do RV - "#". Como resultado, obtemos uma expressão regular ( r)#.

Construindo uma árvore

Vamos imaginar uma expressão regular como uma árvore, cujas folhas são os caracteres terminais, e os nós internos são as operações de concatenação ".", união "∪" e iteração "*". Atribuímos um número único a cada folha da árvore (exceto para folhas ε) e nos referimos a ele, por um lado, como a posição na árvore e, por outro, como a posição do símbolo correspondente ao folha.

Cálculo de funções anuláveis, firstpos, lastpos

Agora, percorrendo a árvore T de baixo para cima da esquerda para a direita, calculamos três funções: anulável, primeiras posições, e lastpos. Funções anulável, primeiras posições e lastpos definido nos nós da árvore. O valor de todas as funções, exceto anulável, é o conjunto de posições. Função primeiras posições(n) para cada nó n da árvore de sintaxe regex fornece o conjunto de posições que correspondem aos primeiros caracteres nas substrings geradas pela subexpressão que termina em n. Da mesma maneira, lastpos(n) fornece o conjunto de posições que correspondem aos últimos caracteres nas substrings geradas por subexpressões com top n. Para nós n, cujas subárvores (ou seja, uma árvore cujo nó né uma raiz) pode gerar uma palavra vazia, definimos anulável(n) = verdadeiro, e para outros nós falso. Tabela para calcular anulável, primeiras posições, lastpos:

nó n	anulável(n)	primeiras posições(n)	lastpos(n)
ε	verdadeiro	∅	∅
eu ≠ ε	falso	{eu}	{eu}
u ∪ v	anulável(você) ou anulável(v)	primeiras posições(você) ∪ primeiras posições(v)	lastpos(você) ∪ lastpos(v)
você . v	anulável(você) e anulável(v)	E se anulável(você) então primeiras posições(você) ∪ primeiras posições(v) senão primeiras posições(você)	E se anulável(v) então lastpos(você) ∪ lastpos(v) senão lastpos(v)
v*	verdadeiro	primeiras posições(v)	lastpos(v)

Construindo acompanhamentos

Função seguimentos calculado via anulável, primeiras posições e lastpos. Função seguimentos definido em várias posições. Significado seguimentosé um conjunto de posições. Se um eu- posição, então seguimentos(eu) existem muitas posições j tal que haja alguma corda ... cd... incluído na linguagem descrita por RW, de modo que eu corresponde a esta entrada c, uma j- entrada d. Função seguimentos também pode ser calculado em uma travessia da árvore de acordo com as duas regras a seguir

1. Deixar n- nó interno com "." (concatenação); uma, b- seus descendentes. Então para cada posição eu incluído em lastpos(uma seguimentos(eu) vários primeiras posições(b).
2. Deixar n- nó interno com operação "*" (iteração), uma- seu descendente. Então para cada posição eu incluído em lastpos(uma), adicione ao conjunto de valores seguimentos(eu) vários primeiras posições(uma).

Exemplo

Calcular valor da função seguimentos para expressão regular ( uma(b|c))*c.

Posição	Significado seguimentos
1: (uma (b|c))*c	{2, 3}
2: (uma(b |c))*c	{1, 4}
3: (uma(b|c ))*c	{1, 4}
4: (uma(b|c))*c	{5}

Criando um DFA

Um DFA é um conjunto de estados e um conjunto de transições entre eles. O estado do DFA é um conjunto de posições. A construção de um DFA consiste na adição gradual dos estados necessários a ele e na construção de transições para eles. Inicialmente, há um estado primeiras posições(raiz) (raiz- a raiz da árvore), que não tem transições. A transição é realizada por caracteres da expressão regular. Cada caractere corresponde a um conjunto de posições ( p eu). Unindo todos seguimentos(x) é o estado para o qual é necessário ir, onde x é uma posição que está presente tanto entre as posições do estado quanto entre as posições do símbolo do RE, sobre o qual é feita a transição. Se não houver tal estado, ele deve ser adicionado. O processo deve ser repetido até que todas as transições para todos os estados sejam construídas. Todos os estados contendo a posição do símbolo # adicionado ao final da RE são declarados finais.

DFA obtido de RV ( uma(b|c))*c

Exemplo

Criar DFA por expressão regular ( uma(b|c))*c.

Estado DKA	Símbolo
	a(1)	b(2)	c(3, 4)
A(1, 4)	B(2, 3)	-	C(5)
B(2, 3)	-	A(1, 4)	A(1, 4)
C(5)	-	-	-

Como criar um DFA com um número mínimo de estados

Um DFA com um número mínimo de estados é construído para um DFA definido em qualquer lugar, ou seja, de tal modo que . Para qualquer DFA, existe um DFA definido em todos os lugares equivalente a ele.

Construção de um DFA definido em todos os lugares

Introduzir um novo estado e definir um novo conjunto de estados .

Vamos definir uma nova função de transição como esta:

Construindo uma partição (formalmente)

Vamos construir a partição inicial P conjuntos de estados em dois grupos: estados finais F e outros S/F, ou seja P = {F, Q\F}.

Aplicar a cada grupo G ∈ P procedimento a seguir. esmagar G em subgrupos para que os estados s e t a partir de G acabou no mesmo grupo se e somente se para cada símbolo de entrada uma estados s e t tem transições uma para estados do mesmo grupo em P.

Os subgrupos resultantes são adicionados à nova partição P novo.

Aceitar P = P novo e repita a construção da divisória até a estabilização, ou seja, até que a divisória pare de mudar.

Construindo uma partição (algoritmo)

Para construir uma partição, existe o seguinte algoritmo. Construímos uma tabela de transição para o autômato original, construímos uma partição inicial.

Atribuímos um identificador a cada grupo da partição (para a partição inicial, por exemplo, 0 e 1).

A cada estado (cada linha da tabela) é atribuída uma string da forma “a.bcd…xyz”, onde é o identificador do grupo ao qual o estado pertence [a primeira coluna (de onde vamos), a segunda coluna (onde vamos pelo primeiro caractere), …, a última coluna (onde vamos pelo último caractere)].

Construímos novos grupos de acordo com a coincidência de strings, ou seja, de modo que estados com as mesmas strings atribuídas caiam em um grupo.

Em seguida, uma nova iteração. Atribuímos novos identificadores aos grupos resultantes, por exemplo (0, 1, ..., n). E repetimos a construção da partição até a estabilização.

Observe que quando há um estado restante no grupo, nas etapas subsequentes da construção da partição, você não pode mais escrever a string de identificadores para esse estado, pois essa string será única em qualquer caso devido ao primeiro caractere do corda. Em outras palavras, ao dividir, nada acontecerá a um grupo de um estado - ele é transferido para uma nova divisão como está.

Construção do autômato reduzido

Cada um dos grupos resultantes se torna o estado de um novo DFA. Se o grupo contém o estado inicial (final) do autômato original, esse grupo se torna o estado inicial (respectivamente final) do novo DFA. As transições são construídas de maneira óbvia: uma transição para um estado de um grupo é considerada uma transição para um grupo.

Nós trazemos a máquina. Primeiro removemos o não gerador (estéril, "morto"), então estados inalcançáveis ​​(as definições são dadas para os símbolos, mas de maneira óbvia são transferidas para os estados do autômato).

De um modo geral, a remoção de estados mortos transforma um DFA em um NFA, pois todas as transições devem ser definidas em um DFA. No entanto, no Livro do Dragão, tal desvio da definição formal ainda é considerado aceitável.

Exemplo

Para construir um DFA com um número mínimo de estados para um DFA da seguinte forma:

• Divisão inicial: (C) ( estado final), (A, B, D, E) ( todos os outros estados).
• (C)( sem alterações), (A, D, E), (B), ( uma vez que passamos de A, D, E ao longo de a, c para B e C, respectivamente).
• Não podemos fazer mais divisões.

Deixe o grupo (C) corresponder ao estado C, o grupo (A, D, E) ao estado A e o grupo (B) ao estado B. Então obtemos um DFA com um número mínimo de estados:

Exemplo (algoritmo para construir uma partição)

Uma tabela de transição para um DFA definido em todos os lugares (estado Z adicionado) correspondente a RV (ab|ε)a*|abb|b*a. Das questões do exame de 2012.

	uma	b	eu 0	eu 1
→A*	B	C	0.01	0.12
B*	D	E	0.00	1.01
C	F	C	1.01
D*	D	Z	0.01	0.04
E*	D	Z	0.00	1.03
F*	Z	Z	0.11
Z	Z	Z	1.11

Iterações:

• I 0: ABCDEF(0), CZ(1).
• I 1: AD(0), BE(1), C(2), F(3), Z(4).
• I 2: A, B, C, D, E, F, Z.

Resultado: a máquina já tinha o número mínimo de estados :-)

DFA que permite a conclusão do idioma

O algoritmo para construir um DFA que aceita o complemento da linguagem L (L̅) consiste em duas etapas:

• Construindo um DFA completo
• Construção do autômato desejado a partir dele

Na verdade, não existe um DFA completo. Sob DKA completo algum os professores entendem o autômato, na tabela de transição da qual não há células vazias. No entanto, de acordo com a definição do DFA - δ: Q × Σ → Q - não pode haver células vazias em nenhum caso. O autômato "com células vazias", no entanto, satisfaz a definição do NFA. No decorrer da resolução, não é incomum obter exatamente esse NFA, que carece apenas de transições antes do DFA.

Para reabastecê-lo, basta adicionar um novo estado X, e as transições inexistentes "em vez de" adicionam transições a esse novo estado. Não se esqueça de adicionar transições de X dentro X. É fácil ver que onde o autômato original não aceitou alguma cadeia devido à ausência de transição, o novo autômato entrará no estado X e se apegue a isso. Como o novo estado não é um estado de aceitação (final), o novo autômato também não aceitará essa cadeia.

Agora, para construir o autômato desejado, basta alterar os papéis dos estados de aceitação e não aceitação. Em outras palavras, F" = Q\F.

Construindo um analisador LL(k)

Transformação gramatical

Nem toda gramática é analisável por LL(k). Uma gramática livre de contexto pertence à classe LL(1) se não tiver conflitos FIRST-FIRST (recursão à esquerda é um caso especial de tal conflito) e FIRST-FOLLOW.

Algumas vezes é possível transformar gramáticas não LL(1) para que se tornem LL(1). Algumas (mais precisamente, aquelas que foram consideradas no curso) transformações são apresentadas a seguir.

Removendo recursão à esquerda

Suponha que tenhamos uma regra da forma (doravante nesta seção, letras maiúsculas - símbolos não terminais, minúsculo - cadeias de qualquer personagem):

• A→A uma| UMA b| … | UMA k | m | n | … | z

Não é passível de análise inequívoca, por isso deve ser convertido.

É fácil mostrar que esta regra é equivalente ao seguinte par de regras:

• A → m b | n b | … | z B
• B → uma b | b b | … | k b | ε

Fatoração à esquerda

A essência deste procedimento é a eliminação da ambiguidade na escolha das regras para o símbolo da esquerda. Para fazer isso, um prefixo comum à esquerda é encontrado e o que pode segui-lo é retirado em uma nova regra (letras minúsculas - cadeias de qualquer personagem)

Exemplo

• A → uma c | uma df | uma dg | b

Convertido para

• A → uma b | b
• B → c | d f | d g

que por sua vez se torna

• A → uma b | b
• B → c | d A PARTIR DE
• C → f | g

Exemplo de conversão gramatical

G= ((S, A, B), (a, b, c), P, S)

• S→SAbB | uma
• A→ab | aa | ε
• B → c | ε

Removendo a recursão à esquerda para S:

• S → aS 1
• S 1 → AbBS 1 | ε

Fatoração à esquerda para A:

• A → aA 1 | ε
• A 1 → b | uma

Gramática final:

• S → aS 1
• S 1 → AbBS 1 | ε
• A → aA 1 | ε
• A 1 → b | uma
• B → c | ε

Construindo PRIMEIRO e SIGA

PRIMEIRO(α), onde α ∈ (N ∪ T)* é o conjunto de terminais a partir do qual α pode começar. Se α ⇒ ε, então ε ∈ PRIMEIRO(α). Assim, o valor do FOLLOW( UMA) para não terminal UMA- muitos terminais que podem aparecer imediatamente após UMA de alguma forma sentimental. Se um UMA pode ser o caractere mais à direita em alguma forma sentencial, então o token $ final também pertence a FOLLOW( UMA)

PRIMEIRO cálculo

Para terminais

• Para qualquer terminal x, x ∈ T, PRIMEIRO( x) = {x}

Para não terminais

• Se um Xé um não-terminal, então colocamos FIRST( X) = {∅}
• Se a gramática tem uma regra X→ ε, então adicione ε a PRIMEIRO( X)
• Para cada não terminal X e para cada regra de inferência X → S 1 …S k adicionar a PRIMEIRO( X) o PRIMEIRO conjunto de todos os símbolos do lado direito da regra até o primeiro do qual ε não é derivado, incluindo seu

Para correntes

• Para cadeia de caracteres X 1 …X k PRIMEIRO é a união dos PRIMEIROS caracteres incluídos na string até o primeiro, que possui ε ∉ PRIMEIRO, incluindo-o.

Exemplo

• S → aS 1
• S 1 → AbBS 1 | ε
• A → aA 1 | ε
• A 1 → b | uma
• B → c | ε

PRIMEIROS não terminais na ordem de resolução de dependência:

• PRIMEIRO(S) = (a)
• PRIMEIRO(A) = (a, ε)
• PRIMEIRO(A 1) = (b, a)
• PRIMEIRO(B) = (c, ε)
• PRIMEIRO(S 1) = (a, b, ε)

PRIMEIRO para regras de inferência:

• PRIMEIRO(aS 1) = (a)
• PRIMEIRO(AbBS 1) = (a, b)
• PRIMEIRO(ε) = (ε)
• PRIMEIRO(aA 1) = (a)
• PRIMEIRO(a) = (a)
• PRIMEIRO(b) = (b)
• PRIMEIRO(c) = (c)

SEGUIR cálculo

Calculando a função FOLLOW para o caractere X:

• Seja SEGUIR(X) = (∅)
• Se X for um axioma gramatical, adicione o marcador $ a FOLLOW
• Para todas as regras da forma A → αXβ adicione FIRST(β)\(ε) a FOLLOW(X) (X pode ser seguido por aqueles caracteres que começam com β)
• Para todas as regras da forma A → αX e A → αXβ, ε ∈ FIRST(β), adicione FOLLOW(A) a FOLLOW(X) (ou seja, X pode ser seguido por todos os caracteres que podem seguir A, se em a regra de inferência, o X pode estar na extrema direita)
• Repita os dois parágrafos anteriores enquanto for possível adicionar caracteres ao conjunto

Exemplo

• S → aS 1
• S 1 → AbBS 1 | ε
• A → aA 1 | ε
• A 1 → b | uma
• B → c | ε

Resultado:

• SEGUIR(S) = ($)
• FOLLOW(S 1) = ($) (S 1 é o caractere mais à direita na regra S → aS 1)
• SEGUIR(A) = (b) (A na regra S 1 → AbBS 1 é seguido por b)
• FOLLOW(A 1) = (b) (A 1 é o caractere mais à direita na regra A → aA 1 , portanto, adicionando FOLLOW(A) a FOLLOW(A 1))
• FOLLOW(B) = (a, b, $) (adicione FIRST(S 1)\(ε) (segue da regra S 1 → AbBS 1), FOLLOW(S 1) (porque existe S 1 → ε))

Compilando uma tabela

Mesa M para um par não-terminal-terminal (na célula M[UMA, uma]) especifica a regra pela qual a palavra de entrada deve ser reduzida. A tabela é preenchida da seguinte forma: para cada regra de inferência de uma dada gramática A → α (onde α é entendido como uma cadeia do lado direito da regra), as seguintes ações são realizadas:

1. Para cada terminal uma∈ PRIMEIRO(α) adicione uma regra UMA → α para M[UMA, uma]
2. Se ε ∈ PRIMEIRO(α), então para cada b∈ SEGUIR( UMA) adicionar UMA → α para M[UMA, b]
3. ε ∈ PRIMEIRO(α) e $ ∈ SEGUIR( UMA), adicionar UMA → α para M[UMA, $]
4. Todas as células vazias são um erro na palavra de entrada

Exemplo

Construir uma tabela para gramática

• S → aS 1
• S 1 → AbBS 1 | ε
• A → aA 1 | ε
• A 1 → b | uma
• B → c | ε

Resultado:

	uma	b	c	$
S	S → aS 1 (Primeira regra, inferência S → aS 1 , a ∈ FIRST(aS 1))	erro (Quarta regra)	erro (Quarta regra)	erro (Quarta regra)
S1	S 1 → AbBS 1 (Primeira regra, saída S 1 → AbBS 1 , a ∈ FIRST(AbBS 1))	S 1 → AbBS 1 (Primeira regra, saída S 1 → AbBS 1 , b ∈ FIRST(AbBS 1))	erro (Quarta regra)	S 1 → ε (Terceira regra, inferência S 1 → ε, ε ∈ PRIMEIRO(ε), $ ∈ SEGUIR(S 1))
UMA	A → aA 1 (Primeira regra, saída A → aA 1 , a ∈ PRIMEIRO(aA 1))	A→ε (Segunda regra, saída A 1 → ε, b ∈ FOLLOW(A 1))	erro (Quarta regra)	erro (Quarta regra)
A 1	A 1 → a (Primeira regra, saída A 1 → a, a ∈ PRIMEIRO(a))	A 1 → b (Primeira regra, saída A 1 → b, b ∈ PRIMEIRO(b))	erro (Quarta regra)	erro (Quarta regra)
B	B→e	B→e (Segunda regra, inferência B → ε, a ∈ FOLLOW(B))	B → c (Primeira regra, saída B → c, c ∈ PRIMEIRO(c))	B→e (Terceira regra, inferência B → ε, $ ∈ FOLLOW(B))

Análise de string

O processo de análise de uma string é bastante simples. Sua essência é a seguinte: a cada passo, o símbolo superior é lido v c cadeia de entrada.

• Se um v- caractere terminal
  • Se um v coincide com Com, então ambos são destruídos, há uma mudança
  • Se um v não combina com Com, então um erro de análise é sinalizado
• Se um v- símbolo não terminal, c retorna ao início da linha em vez de v o lado direito da regra, que é retirado da célula da tabela, é devolvido à pilha M[v, c]

O processo termina quando a string e a pilha atingem o marcador final (#).

Exemplo

Vamos analisar a string "aabbaabcb":

pilha	linha	ação
S#	uma abbaabcb$	S → aS 1
uma S1#	uma abbaabcb$	mudança
S1#	uma bbaabcb$	S 1 → AbBS 1
UMA bbs 1#	uma bbaabcb$	A → aA 1
uma A 1 bBS 1 #	uma bbaabcb$	mudança
A 1 bbs 1#	b baabcb$	A 1 → b
b bbs 1#	b baabcb$	mudança
b B.S. 1#	b aabcb$	mudança
B S1#	uma abcb$	B→e
S1#	uma abcb$	S 1 → AbBS 1
UMA bbs 1#	uma abcb$	A → aA 1
UMA bbs 1#	uma abcb$	A → aA 1
uma A 1 bBS 1 #	uma abcb$	mudança
A 1 bbs 1#	uma bcb$	A 1 → a
uma bbs 1#	uma bcb$	mudança
b B.S. 1#	b cb$	mudança
B S1#	c b$	B → c
c S1#	c b$	mudança
S1#	b$	S 1 → AbBS 1
UMA bbs 1#	b$	A→ε
b B.S. 1#	b$	mudança
B S1#	$	B→e
S1#	$	S 1 → ε
#	$	pronto

Construindo um analisador LR(k)

Calculando k em LR(k)

Não há algoritmo que permita, no caso geral, calcular k para uma gramática arbitrária. Geralmente vale a pena tentar construir um analisador LR(1). Se tiver no máximo uma operação por conjunto (Shift, Reduce ou Accept), então a gramática é LR(0). Se, no entanto, ocorrer um conflito e uma colisão ao construir um analisador LR(1), então essa gramática não é LR(1) e vale a pena tentar construir LR(2). Se ele falhar em construí-lo, então LR(3) e assim por diante.

Conclusão gramatical

Vamos adicionar uma nova regra S" → S, e fazer S" um axioma da gramática. Essa regra adicional é necessária para determinar quando o analisador termina e a cadeia de entrada é permitida. A admissão ocorre se e somente se for possível realizar a convolução de acordo com a regra S → S".

Construção de um sistema canônico de conjuntos de situações LR(1) admissíveis

No início, há um conjunto I 0 com a configuração do analisador S" → .S, $. Em seguida, a operação de fechamento é aplicada a esta configuração até que, como resultado de sua aplicação, não sejam adicionadas novas configurações. , as transições para novos conjuntos são construídas deslocando o ponto um caractere para a direita (os saltos são feitos pelo caractere que estava depois do ponto antes do salto e antes dele após o salto), e as configurações que foram obtidas das existentes desta forma são adicionados a esses conjuntos, a operação de fechamento também é aplicada a eles, e todo o processo é repetido até que não apareçam mais novos conjuntos.

Exemplo

Construa um sistema canônico de conjuntos de situações LR(1) admissíveis para a gramática especificada:

• S" → S
• S → ABA
• A → Aa | ε
• B → cBc | d

Solução:

• Construímos um closure para a configuração S" → .S, $:
  • S → .ABA,$
• Para as configurações resultantes (S → .ABA, $) também construímos um closure:
  • A → .Aa, c
  • A → .Aa, d
  • A → .,c
  • A → ., d
• Para as configurações resultantes (A → .Aa, c; A → .Aa, d) também construímos um fechamento:
  • A → .Aa, a
  • A → ., a
• Não é possível construir mais configurações no estado I 0 - o fechamento é construído

• A partir de I 0, você pode fazer transições ao longo de S e A e obter um conjunto de configurações I 1 e I 2, composto pelos seguintes elementos:
  • I 1 = (S" → S., $)
  • I 2 = (S → A.BA, $; A → A.a, c; A → A.a, d; A → A.a, a)
• I 1 não requer fechamento
• Vamos construir o fechamento I 2:
  • B → .cBc, a
  • B → .cBc, $
  • B → .d, a
  • B → .d, $
• Todos os outros conjuntos são construídos de forma semelhante.

Construindo a tabela do analisador

O passo final na construção de um analisador LR(1) é construir tabelas ação e Vá para. Mesa ação construído para caracteres de string de entrada, ou seja, para terminais e marcador de fim de linha $, tabela Vá paraé construído para símbolos gramaticais, ou seja, para terminais e não terminais.

Construindo uma tabela Goto

A tabela Goto mostra para qual estado ir quando o próximo símbolo gramatical for encontrado. Portanto, se no sistema canônico de conjuntos há uma transição de eu eu dentro eu j pelo símbolo A, então em Goto( EU eu, A) colocamos o estado EU j. Após preencher a tabela, assumimos que em todas as células vazias Goto( EU eu, A) = Erro

Construindo a tabela de ações

• Se houver uma transição no terminal a do estado I i para o estado I j , então Action(I i , a) = Shift(I j)
• Se A ≠ S" e existe uma configuração A → α., a, então Ação(I i , a) = Reduzir(A → α)
• Para um estado I i que tem uma configuração S" → S., $, Action(I i , $) = Accept
• Para todas as células vazias Action(I i , a) = Error

Exemplo

Construir tabelas Action e Goto para gramática

• S" → S
• S → ABA
• A → Aa | ε
• B → cBc | d

Solução:

	ação				Vá para
	uma	c	d	$	S	S"	UMA	B	uma	c	d
eu 0	Reduzir(A → ε)	Reduzir(A → ε)	Reduzir(A → ε)		eu 1		eu 2
eu 1				Aceitar
eu 2	Turno (I 6)	Turno (I 4)	Turno (I 5)					eu 3	eu 6	eu 4	eu 5
eu 3	Reduzir(A → ε)			Reduzir(A → ε)			eu 13
eu 4		Turno (I 8)	Turno (I 9)					eu 7		eu 8	eu 9
eu 5	Reduzir(B → d)			Reduzir(B → d)
eu 6	Reduzir(A → Aa)	Reduzir(A → Aa)	Reduzir(A → Aa)
eu 7		Turno (I 10)								eu 10
eu 8		Turno (I 8)	Turno (I 9)					eu 11		eu 8	eu 9
eu 9		Reduzir(B → d)
eu 10	Reduzir(B → cBc)			Reduzir(B → cBc)
eu 11		Turno (I 12)								eu 12
eu 12		Reduzir(B → cBc)
eu 13	Turno (I 14)			Reduzir(S → ABA)					eu 14
eu 14	Reduzir(A → Aa)			Reduzir(A → Aa)

Análise de cadeia

A cada passo, o caractere do topo é lido v da pilha do analisador e pegue o último caractere c cadeia de entrada.

Se na tabela de ações na interseção v e c localizado:

• Mudança( Ik), em seguida, coloque na pilha Com e depois Ik. Em que c removido da corda.
• Reduzir( UMA → você), então todos os símbolos terminais e não terminais que compõem a cadeia são apagados do topo da pilha você, após o que o Estado olha Eu estou permanecendo no topo. De acordo com a tabela de transição na interseção Eu estou e UMA encontre o próximo estado É. Então A é empurrado para a pilha, e então É. A linha permanece inalterada.
• Aceite, então a análise está concluída
• o vazio é um erro

Exemplo

Vamos construir a análise da string aaaccdcc:

Pilha	Linha	Ação
eu 0	uma aaccdcc$	Reduza(A → ε), vá para I 2
Eu 0 A eu 2	uma aaccdcc$	Turno (I 6)
I 0 A I 2 a eu 6	uma accdcc$	Reduza (A → Aa), vá para I 2
Eu 0 A eu 2	uma accdcc$	Turno (I 6)
I 0 A I 2 a eu 6	uma ccdcc$	Reduza (A → Aa), vá para I 2
Eu 0 A eu 2	uma ccdcc$	Turno (I 6)
I 0 A I 2 a eu 6	c dcc$	Reduza (A → Aa), vá para I 2
Eu 0 A eu 2	c dcc$	Turno (I 4)
I 0 A I 2 s eu 4	c dcc$	Turno (I 8)
I 0 A I 2 c I 4 c eu 8	d cc$	Turno (I 9)
I 0 A I 2 c I 4 c I 8 d eu 9	c c$	Reduza(B → d), vá para I 11
I 0 A I 2 c I 4 c I 8 B eu 11	c c$	Turno (I 12)
I 0 A I 2 c I 4 c I 8 B I 11 c eu 12	c$	Reduza (B → cBc), vá para I 7
I 0 A I 2 c I 4 B eu 7	c$	Turno (I 10)
I 0 A I 2 c I 4 B I 7 c eu 10	$	Reduza(B → cBc), vá para I 3
I 0 A I 2 B eu 3	$	Reduza(A → ε), vá para I 13
I 0 A I 2 B I 3 A eu 13	$	Reduza (S → ABA), vá para I 1
Eu 0 S eu 1	$	Aceitar

Tradução de expressões aritméticas (algoritmo Seti-Ullman)

Observação. O código é gerado pelo estilo cachorrinho da Motorola, ou seja,

Op Arg1, Arg2

apoia

Arg2 = Arg1 Op Arg2

Construindo uma árvore

A árvore é construída como de costume para uma expressão aritmética: na raiz, a operação com a prioridade mais baixa, seguida pelas operações com prioridade um pouco mais alta e assim por diante. Os parênteses têm a precedência mais alta. Se houver várias operações com a mesma prioridade - a op b op c, então a árvore é construída como para a expressão (a op b) op c.

Exemplo

Construa uma árvore para a expressão a + b / (d + a − b × c / d − e) + c × d

Solução: Escrevemos a expressão na forma

((a) + ((b) / ((((d) + (a)) − ((b) × (c)) / (d)) − (e)))) + ((c) × ( e))

Então na raiz de cada subárvore haverá uma operação, e as expressões entre colchetes à esquerda e à direita dela serão suas subárvores. Por exemplo, para a subexpressão ((b) × (c)) / (d), a operação “/” estará na raiz da subárvore correspondente, e as subexpressões ((b) × (c)) e (d) ) serão suas subárvores.

Layout de árvore (cálculo do número de registros)

• Se o vértice for a folha esquerda (ou seja, uma variável), então o marcamos com zero.
• Se o vértice é a folha direita, então marcamos com um
• Se marcarmos ambas as suas subárvores para algum vértice, então o marcaremos da seguinte forma:
  • Se as subárvores esquerda e direita forem rotuladas com números diferentes, escolha a maior delas
  • Se as subárvores esquerda e direita são rotuladas com os mesmos números, então esta subárvore recebe um número maior do que aquele que rotula as subárvores

marcas de folhas	Layout de árvore com subárvores idênticas	A subárvore esquerda é rotulada com um grande número	A subárvore direita é rotulada com um grande número

certo - mesmo como um ancestral.

Se o rótulo deixei descendente mais rótulos certo, então certo criança é atribuída registrar mais um do que o antepassado, e deixei - mesmo como um ancestral.

O código é formado percorrendo a árvore de baixo para cima da seguinte forma:

1. Nenhum código é gerado para o vértice com rótulo 0

2. Se o topo for a folha X com etiqueta 1 e registrar R eu, então o código

MOVER X, Ri

3. Se o topo for interno com registrador R eu e seu filho esquerdo é a folha X com rótulo 0, então corresponde ao código

<Код правого поддерева>OpX, Ri

4. Se subárvores de um vértice com registrador R eu- não sai e o rótulo do vértice direito é maior ou igual ao rótulo do esquerdo (que tem o registrador Rj, j = i + 1), então o código corresponde ao vértice

<Код certo subárvore><Код deixei subárvores > Op Rj, Ri

5. Se as subárvores do vértice com registrador R eu- não sai e o rótulo do vértice direito (para o qual o registrador Rj, j = i + 1) é menor que o rótulo do vértice esquerdo, então o código corresponde ao vértice

A distribuição de registradores é mostrada no gráfico à direita. Código gerado:

MOVE d, R0 ;R0 = d MOVE c, R1 ;R1 = c MUL b, R1 ;R1 = (b × c) DIV R1, R0 ;R0 = (b × c) / d MOVE a, R1 ;R1 = a ADD d, R1 ;R1 = a + d SUB R1, R0 ;R0 = (a + d) − ((b × c) / d) MOVE e, R1 ;R1 = e SUB R0, R1 ;R1 = ((a + d) − ((b × c) / d)) − e MOVER R1, R0;R0 = ((a + d) − ((b × c) / d)) − e DIV b, R0 ;R0 = b / (((a + d) − ((b × c) / d)) − e) ADICIONE a, R0 ;R0 = a + (b / (((a + d) − ((b × c) / d) )) − e)) MOVE d, R1 ;R1 = d MUL c, R1 ;R1 = c × d ADICIONE R0, R1 ;R1 = (a + (b / (((a + d)) − ((b × c) ) / d)) − e))) + (c × d) MOVER R1, R0;R0 = (a + (b / (((a + d) − ((b × c) / d)) − e) )) + (c × d)

Tradução de expressões lógicas

Esta seção mostra como gerar código para avaliação lenta de expressões booleanas. Como resultado do algoritmo, obtém-se um trecho de código que, utilizando as operações TST, BNE, BEQ, calcula uma expressão lógica alternando para um dos rótulos: TRUELAB ou FALSELAB.

Construindo uma árvore

A árvore de uma expressão lógica reflete a ordem em que ela é avaliada de acordo com a precedência das operações, ou seja, para avaliar o valor de um nó de árvore (que é uma operação sobre dois operandos que são subárvores do nó), devemos primeiro calcule os valores de suas subárvores.

Prioridade de operação: O operador NOT tem a precedência mais alta, seguido por AND e OR. Se outras operações lógicas forem usadas na expressão, elas devem ser expressas por meio dessas três de uma certa maneira (geralmente, não há outras operações e a conversão de expressão não é necessária). A associatividade para operações de mesma prioridade é da esquerda para a direita, ou seja, A e B e C são tratados como (A e B) e C

Exemplo

Construa uma árvore para a expressão lógica não A ou B e C e (B ou não C).

Solução: veja o diagrama à direita.

Para cada vértice da árvore, 4 atributos são calculados:

• Número do nó
• O rótulo para o qual pular se a expressão no nó for falsa (rótulo falso, fl)
• O rótulo para o qual pular se a expressão no nó for verdadeira (rótulo verdadeiro, tl)
• Etiqueta-sinal (sinal) (para mais detalhes, veja abaixo)

Os vértices são numerados em ordem aleatória, a única condição é a unicidade dos números dos nós.

O layout da árvore é feito da seguinte forma:

• fl especifica o número do vértice para o qual a transição é feita ou falselab se este vértice for falso
• tl indica o número do vértice para o qual a transição é feita ou truelab se este vértice for verdadeiro

Sign especifica em qual caso a avaliação da subárvore atual pode ser encerrada.

Para a raiz da árvore, fl=falselab, tl=truelab, sign=false.

Nesse caminho:

Exemplo

Marque a árvore construída para a expressão lógica não A ou B e C e (B ou não C).

Geração de código

Comandos de máquina usados ​​no código gerado:

• TST - verificando o argumento para veracidade e definindo um sinalizador se o argumento for falso
• BNE - pular para o rótulo se o sinalizador não estiver definido, ou seja, a condição verificada com TST verdadeiro
• BEQ - pular no rótulo se o sinalizador estiver definido, ou seja, a condição verificada com TST falso

O código é construído da seguinte forma:

• a árvore é percorrida a partir da raiz, para AND e OR, a subárvore esquerda é percorrida primeiro, depois a direita
• para cada vértice passado, seu número (rótulo) é impresso
• para folha A(número, tl, fl, sinal) TST A é impresso
  • se sinal == verdadeiro, BNE tl é impresso
  • if sign == false, BEQ fl é impresso

Exemplo

Para a expressão acima, o seguinte código será gerado:

1:2:4: TST A BEQ TRUELAB 3:5:7: TST B BEQ FALSELAB 8: TST C BEQ FALSELAB 6:9: TST B BNE TRUELAB 10:11: TST C BNE FALSELAB TRUELAB: FALSELAB:

Método de correspondência de amostra

A ideia do método é que, para uma mesma seção do programa, o código possa ser gerado de diferentes maneiras e, como resultado, a otimização possa ser alcançada para um ou outro parâmetro.

Formulação do problema

Existem muitas amostras, cada uma das quais é definida por uma parte da representação intermediária para a qual é aplicável, o peso e o código gerado. Existe uma árvore de representação intermediária, que é um fragmento do programa para o qual é necessário gerar código. O objetivo é construir tal cobertura da árvore de representação intermediária com amostras de modo que o peso total das amostras seja mínimo.

Os padrões são instruções de montagem e as árvores de análise que correspondem a elas. Para cada amostra, seu tempo de execução (em ciclos) é conhecido. Com a ajuda deles, geraremos o código ideal (em termos de tempo de execução).

Exemplos de amostra

Construindo uma representação intermediária

Primeiro, construímos uma árvore de análise para toda a expressão.

Construindo uma cobertura

Agora, para cada vértice (passamos por eles na ordem das folhas até a raiz), geraremos o código ideal para sua subárvore. Para fazer isso, simplesmente passamos por todas as amostras que são aplicáveis ​​em um determinado vértice. O tempo de execução ao usar um determinado padrão será a soma do tempo necessário para avaliar seus argumentos (e já sabemos o código ideal para calculá-los graças à ordem de travessia da árvore) e o tempo de execução do próprio padrão. De todas as opções obtidas, escolhemos a melhor - será o código ideal para a subárvore deste vértice. Na raiz da árvore, obtemos o código ideal para toda a expressão.

Geração de código

Não é necessário escrever o código para todos os vértices - basta anotar o tempo mínimo necessário e a amostra que você precisa usar. Tudo o resto é facilmente restaurado.

Temos um número infinito de registradores nesses problemas, então a cada vez você pode usar um novo.

Construção de RV de acordo com DKA

Construção do NFA de acordo com a gramática linear direita

Fundição de gramática

Para converter uma gramática COP arbitrária para a forma reduzida, você deve executar as seguintes etapas:

• remova todos os caracteres estéreis;
• remova todos os caracteres inacessíveis;

Removendo caracteres inúteis

Entrada: COP-gramática G = (T, N, P, S).

Saída: Uma gramática COP G' = (T, N', P', S) não contendo símbolos estéreis, para os quais L(G) = L(G').

Método:

Construa recursivamente os conjuntos N 0 , N 1 , ...

1. N 0 = ∅, i = 1.
2. N i = (A | (A → α) ∈ P e α ∈ (N i - 1 ∪ T)*) ∪ N i-1 .
3. Se N i ≠ N i - 1, então i = i + 1 e vá para o passo 2, caso contrário N' = N i ; P' consiste em regras do conjunto P contendo apenas símbolos de N' ∪ T; G' = (T, N', P', S).

Definição: um símbolo x ∈ (T ∪ N) é dito inalcançável em uma gramática G = (T, N, P, S) se não aparece em nenhuma forma sentencial desta gramática.

Exemplo

Remova caracteres inúteis da gramática G((A, B, C, D, E, F, S), (a, b, c, d, e, f, g), P, S)

• S → AcDe | CaDbCe | Saca | aCb | dFg
• A → SeAd | cSA
• B → CaBd | aDBc | BSC | namorado
• C→Ebd | Seb | aAc | cfF
• D→fCE | ac | dEdAS | ε
• E→ESacD | ae | eFF

Solução

• N 0 = ∅
• N 1 = (B (B → bfg) , D (D → ac) , E (E → aec) )
• N 2 = (B, D, E, C (C → Ebd) )
• N 3 = (B, D, E, C, S (S → aCb))
• N 4 \u003d (B, D, E, C, S) \u003d N 3

G"((B, C, D, E, S), (a, b, c, d, e, f, g), P", S)

• S → CaDbCe | Saca | aCb
• B → CaBd | aDBc | BSC | namorado
• C→Ebd | Seb
• D→fCE | ac | ε
• E→ESacD | ae

Removendo caracteres inacessíveis

Entrada: Gramática COP G = (T, N, P, S)

Saída: Uma gramática COP G' = (T', N', P', S) não contendo símbolos inalcançáveis, para os quais L(G) = L(G').

Método:

1. V0 = (S); e = 1.
2. V i = (x | x ∈ (T ∪ N), (A → αxβ) ∈ P e A ∈ V i - 1 ) ∪ V i-1 .
3. Se V i ≠ V i - 1 , então i = i + 1 e vá para o passo 2, caso contrário N’ = V i ∩ N; T' = V i ∩ T; P' consiste nas regras do conjunto P contendo apenas símbolos de Vi; G' = (T', N', P', S).

Definição: Diz-se que uma gramática COP G é reduzida se não contiver símbolos inatingíveis e estéreis.

Exemplo

Remova os caracteres inacessíveis da gramática G"((B, C, D, E, S), (a, b, c, d, e, f, g), P", S)

• S → CaDbCe | Saca | aCb
• B → CaBd | aDBc | BSC | namorado
• C→Ebd | Seb
• D→fCE | ac | ε
• E→ESacD | ae

Solução

• V 0 = (S)
• V 1 = (S, C (S → CaDbCe), D (S → CaDbCe), a (S → CaDbCe), b (S → CaDbCe), e (S → CaDbCe))
• V 2 = (S, C, D, a, b, e, E (C → Ebd) , d (C → Ebd) , f (D → fCE) )
• V 3 = (S, C, D, E, a, b, d, e, f, c (E → ESacD) )
• V 4 \u003d (S, C, D, E, a, b, d, e, f, c) \u003d V 3

G""((C, D, E, S), (a, b, c, d, e, f), P"", S)

• S → CaDbCe | Saca | aCb
• C→Ebd | Seb
• D→fCE | ac | ε
• E→ESacD | ae

É mais conveniente descrever o vocabulário de um idioma na forma de expressões regulares e reconhecer um idioma com a ajuda do KA. Portanto, é importante ser capaz de converter definições de linguagem na forma de expressões regulares em uma definição na forma de um FA. Tal transformação foi sugerida por Kennet Thompson.

A máquina de estado é um cinco (S, S, d, S 0 , F)

S é um conjunto finito de estados.

S é um conjunto finito de sinais de entrada admissíveis.

d - função de transição. Ele reflete o conjunto Sx(SÈ(e)) no conjunto de estados de um autômato finito não determinístico. Para um autômato determinístico, a função de transição reflete o conjunto SxS no conjunto de estados do autômato. Em outras palavras, dependendo do estado e do símbolo de entrada, d determina o novo estado do autômato.

S 0 - estado inicial do autômato finito, S 0 О S.

F é o conjunto de estados finais do autômato, F О S.

A operação de uma máquina de estado é uma sequência de etapas. A etapa é determinada pelo estado do autômato e pelo símbolo de entrada. A etapa em si consiste em mudar o estado do autômato e ler o próximo símbolo da sequência de entrada.

Existem as seguintes regras para converter expressões regulares em uma máquina de estado.

1 A expressão regular “e” é transformada em um autômato de dois estados e uma e-transição entre eles (Figura 1).

Figura 1. - Autômato para e-transição

2 Uma expressão regular de um caractere “a” é convertida em uma máquina de estados finitos a partir de dois estados e uma transição entre eles de acordo com o sinal de entrada a (Figura 2).

Figura 2. - Autômato para salto pelo símbolo a

3 Seja uma expressão regular rs e autômatos finitos para a expressão r e a expressão s já foram construídas. Então os dois autômatos são conectados em série. A Figura 3 mostra os autômatos iniciais para as linguagens r e s. A figura mostra um autômato para reconhecer a concatenação dessas linguagens.

Automático para r Automático para s

Figura 3. - Autômatos iniciais

Figura 4. - Máquina para concatenar linguagens

4 Seja uma expressão regular r | s e autômatos finitos já foram construídos para a expressão r e a expressão s (Figura 3). Então no autômato resultante deve haver uma alternativa de executar um dos dois autômatos. Ou seja, o autômato para a expressão r | s para autômatos para r e s da Figura 3 tem a forma mostrada na Figura 5.

Figura 5. - Máquina para combinar linguagens

5 Seja uma expressão regular r* com o autômato finito construído r. Neste caso, são introduzidos dois novos estados para a possibilidade de contornar o autômato da expressão r, e uma e-transição entre os estados final e inicial é introduzida para a possibilidade de repetição múltipla do autômato r. Se um autômato semelhante ao da Figura 3 é construído para a expressão regular r, então o autômato finito mostrado na Figura 6 corresponde à expressão regular r*.

Definições

De acordo com o teorema de Kleene, qualquer expressão regular pode ser associada a um autômato finito, que é um modelo formal do algoritmo de reconhecimento de lexemas denotados por essa expressão regular. Em termos mais gerais, um autômato-reconhecidor finito é definido por um conjunto finito de estados de fluxo de entrada característicos dele e transições entre eles. Uma mudança de estado ocorre quando os caracteres do fluxo de entrada são recebidos do alfabeto fornecido de acordo com a função de transição , que determina os possíveis estados subsequentes do caractere de entrada e do estado atual. Dentre os estados possíveis, destacam-se os estados inicial (inicial) e final (permitindo), nos quais o autômato-reconhecidor finito pode ser localizado, respectivamente, no início e no término do processamento de tokens do fluxo de entrada. Se a sequência de caracteres de entrada pode gerar uma sequência de transições que pode transferir o autômato finito do estado inicial para um dos finais, então ele é considerado admitido e pertence ao conjunto regular que reconhece.

(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*

tabela 1

	0	1
Q1	Q4	Q2
Q2	Q3	Q1
Q3	Q2	Q4
Q4	Q1	Q3

As colunas da tabela de transição representam os caracteres do alfabeto de entrada e as linhas correspondem aos estados atuais do DFA. Os elementos de cada linha indicam os estados do DFA para os quais ele deve fazer a transição do estado atual ao receber os caracteres correspondentes do alfabeto de entrada. Em particular, segue da primeira linha desta tabela de transição que receber os símbolos 0 e 1 no estado inicial Q1 transfere o DFA para os estados Q4 e Q2, respectivamente.

Ao reconhecer a sequência de entrada da tabela de transição, é fácil rastrear as mudanças de estado do DFA para determinar se um dos estados de aceitação foi alcançado ou não. Em particular, para um vetor binário 01001000 com número par de zeros e uns, o DFA considerado gera a seguinte sequência de transições, onde cada transição é rotulada com o caractere do alfabeto de entrada que a chama:

Q1 0 Q4 1 Q3 0 Q2 0 Q3 1 Q4 1 Q1 0 Q4 0 Q1

Esta sequência de transições termina com o estado de aceitação Q1, portanto, o vetor binário 01001000 pertence ao conjunto regular reconhecido pelo DFA considerado e satisfaz a expressão regular acima.

Em conclusão, deve-se notar que o método informal considerado de construção

Expressões regulares (REs) são uma forma muito conveniente de escrever as chamadas linguagens regulares ou automáticas. Portanto, o RT é usado como linguagem de entrada em muitos sistemas que processam cadeias. Considere exemplos de tais sistemas:

• O comando grep do Unix, ou comandos semelhantes para pesquisar strings, como encontrados em navegadores da Web ou sistemas de formatação de texto. Nesses sistemas, as REs são usadas para descrever padrões que o usuário está procurando em um arquivo. Vários mecanismos de pesquisa convertem o RT em uma máquina de estado finito determinístico (DFA) ou em uma máquina de estado finito não determinístico (NFA) e aplicam essa máquina de estado ao arquivo que está sendo pesquisado.
• Geradores de analisadores léxicos. Os analisadores léxicos são um componente do compilador, eles dividem o programa fonte em unidades lógicas (tokens), que podem consistir em um ou mais caracteres e ter um determinado significado. O gerador do analisador léxico pega as descrições formais dos tokens, que são essencialmente REs, e cria um DFA que reconhece qual token aparece em sua entrada.
• RT em linguagens de programação.

Neste artigo, primeiro nos familiarizaremos com autômatos finitos e seus tipos (DFA e NFA) e, em seguida, consideraremos um exemplo de construção de um DFA mínimo usando uma expressão regular.

Máquinas de estado

Um autômato finito (AF) é um conversor que permite associar uma entrada com uma saída correspondente, e essa saída pode depender não só da entrada atual, mas também do que aconteceu antes, na pré-história do autômato finito. Mesmo o comportamento humano, e não apenas sistemas artificiais, pode ser descrito usando CA. Usando KA, pode-se descrever não apenas o comportamento de sistemas artificiais, mas até mesmo o comportamento humano. Por exemplo, sua reação ao fato de seu vizinho ouvir música alta à noite será uma após a primeira ocorrência e completamente diferente após várias dessas ocorrências. Pode haver um número infinito de tais histórias de fundo, surge a questão; Que tipo de memória uma espaçonave deve ter para se comportar de maneira diferente para cada pré-arranjo? É claro que não é possível armazenar um número infinito de pré-história. Portanto, o autômato, por assim dizer, divide toda a pré-história possível em classes de equivalência. Duas histórias são equivalentes se afetarem igualmente o comportamento do autômato no futuro. A classe de equivalência à qual o autômato atribuiu sua história atual também é chamada de estado interno do autômato.

Agora vamos ver as maneiras pelas quais a CA pode ser especificada. Eles podem ser especificados na forma de gráficos ou na forma de tabelas de controle. Na forma de um gráfico, o KA é especificado da seguinte maneira:

• os vértices do grafo correspondem aos estados do CA.
• arestas direcionadas correspondem a funções de transição (perto de cada aresta, o símbolo ao longo do qual a transição é executada é indicado).
• um vértice com uma aresta entrando nele que não deixa mais de um estado corresponde ao estado inicial.
• os estados finais do CA são marcados com um contorno em negrito.

Na forma de uma tabela de controle, assim:

• Os estados KA estão localizados nas linhas da tabela.
• caracteres do idioma reconhecido - em colunas.
• na interseção, o estado é indicado, que pode ser alcançado a partir do estado dado pelo símbolo dado.

Um exemplo de KA na forma de gráfico e na forma de tabela de controle será apresentado a seguir.

DKA e NKA

A principal diferença entre um DFA e um NFA é que o DFA só pode estar em um estado durante a operação, enquanto o NFA pode estar em vários estados ao mesmo tempo. Como exemplo do trabalho da NCA, pode-se citar a ideia do físico americano Hugh Everett de que qualquer evento divide o mundo em vários mundos, em cada um dos quais esse evento terminou à sua maneira. Por exemplo, em um mundo, Hitler ganhou o 2º Mundo. guerra, em outro - Newton em vez da física entrou no negócio e a descoberta das leis da mecânica clássica teve que ser adiada por 50 anos. Para tirar conclusões da operação da máquina, deve-se estudar todos os "mundos". Após a leitura de toda a cadeia de entrada, assumimos que o NFA aceita essa cadeia se tiver concluído seu trabalho em um estado de aceitação em pelo menos um dos muitos "mundos". Assim, o autômato rejeita o degrau se ele terminou em um estado não aceitável em cada "mundo". O DFA, por outro lado, aceita uma string, isso é óbvio se, depois de ler toda a string de entrada, ele se encontra em um estado de aceitação.

Na maioria dos casos, construir um NFA é muito mais fácil do que construir um DFA. Mas, apesar disso, usar NFA para modelagem não é uma boa ideia. Felizmente, para cada NFA é possível construir um DFA que aceite a mesma linguagem de entrada. Neste artigo, não apresentaremos um algoritmo para construir um DFA a partir de um NFA, mas consideraremos esse algoritmo com base em um exemplo visual abaixo.

Construindo um DFA mínimo a partir de uma expressão regular

Para começar, aqui está a sintaxe RW usada neste artigo:

• a concatenação é especificada com um espaço ou uma string vazia (por exemplo: ab)
• união, usando o símbolo "|"
• iteração (fechamento Kleene), com o caractere "*"

Considere um exemplo dado uma expressão regular:

xy* (x | y*) | ab (x | y*) | (x | a*) (x | y*)

É necessário construir um DFA mínimo a partir de uma expressão regular e demonstrar o reconhecimento de uma string correta e incorreta.

Para começar, simplificamos este RT, usando a lei distributiva da concatenação da mão direita em relação à união, obtemos o seguinte RT:

(xy* | ab | (x | a*)) (x | y*)

Agora construímos um autômato para este RV:

De acordo com a regra de transformação de concatenação (não daremos as regras para transformar RV em KA, pois são bastante óbvias), obtemos o seguinte autômato:

Pela regra de transformação sindical:

De acordo com a regra de transformação de concatenação:

E no final aplicamos a regra de transformação de fechamento e obtemos εNCA:

Nós nos livramos das transições ε (“asterisco” denota estados finais):

Neste NFA, os estados s3 e s5 são equivalentes, pois δ(s3, x) = δ(s5, x) = s1 e δ(s3, y) = δ(s5, y) = s5, s7. Renomeie os estados s6 -> s5 e s7 -> s6:

Construímos o DFA de acordo com o NFA:

Neste DFA, os estados p1 e p5 são equivalentes, pois
δ(p1, x) = δ(p5, x) = p4 e δ(p1, y) = δ(p5, y) = p5. Renomeie os estados p6 -> p5 e p7 -> p6:

Este autômato é o DFA mínimo.

Seja δ a função de transição, então a função de transição estendida construída a partir de δ será denotada por δ', e ω é a string de entrada.

Seja a cadeia ω = aaax como entrada, esperamos que o autômato esteja em um dos estados de aceitação.

δ'(p0, ε) = p0
δ'(p0, a) = δ(δ'(p0, ε), a) = δ(p0, a) = p3
δ'(p0, aa) = δ(δ'(p0, a), a) = δ(p3, a) = p5
δ'(p0, aaa) = δ(δ'(p0, aa), a) = δ(p5, a) = p5
δ'(p0, aaax) = δ(δ'(p0, aaa), a) = δ(p5, a) = p4

p4 é um estado final válido, então a string aaax é válida para este autômato.

Agora suponha que ω = xyyb:

δ'(p0, ε) = p0
δ'(p0, x) = δ(δ'(p0, ε), x) = δ(p0, x) = p1
δ'(p0, xy) = δ(δ'(p0, x), y) = δ(p1, y) = p1
δ'(p0, xyy) = δ(δ'(p0, xy), y) = δ(p1, y) = p1
δ'(p0, xyyb) = δ(δ'(p0, xyy), b) = δ(p1, b) = ∅

Aqui vemos que se o símbolo b for inserido no autômato quando estiver no estado p1, então este autômato morrerá, portanto a cadeia xyyb está incorreta.

P.S. Neste artigo, foi considerado o algoritmo para construção de um DFA por RT, mas existem algoritmos mais convenientes, em particular para programação, mas isso é assunto para outro artigo ...

Para um estudo mais aprofundado das propriedades de autômatos finitos e, em particular, para resolver o problema de síntese, o seguinte teorema é importante.

Teorema 7.7 (teorema da determinização). Para qualquer autômato finito, um autômato finito determinístico equivalente pode ser construído.

Para provar o teorema, é necessário, primeiro, descrever o algoritmo para construir um autômato finito determinístico a partir do original; em segundo lugar, justifique esse algoritmo provando rigorosamente que ele realmente fornece um autômato finito que é determinístico e equivalente ao original. Aqui apresentamos apenas o algoritmo para construir um autômato determinístico.

A transformação de um autômato finito arbitrário em um determinístico equivalente é realizada em duas etapas: primeiro, os arcos com o rótulo \lambda são removidos e, em seguida, a determinação real é realizada.

1. Remoção de transições λ (arcos rotulados \lambda ).

Para mover da máquina de estado original M=(V,Q,q_0,F,\delta) para o autômato finito equivalente M"=(V,Q",q_0,F",\delta") sem transições λ, é suficiente realizar as seguintes transformações no grafo original M.

uma. Todos os estados, exceto o estado inicial, que são inseridos apenas por arcos rotulados \lambda , são removidos; isso define o conjunto Q" do autômato finito M" . É claro que Q"\subseteq Q . Neste caso, assumimos que o estado inicial permanece o mesmo.

b. O conjunto de arcos do autômato finito M" e seus rótulos (portanto, a função de transição M" ) é definido como segue: para quaisquer dois estados p,r\in Q",~ p\to_(a)r vale se e somente se a\in V , e um dos seguintes vale no grafo M: ou existe um arco de p a r cujo rótulo contém o símbolo a, ou existe um estado q tal que p\Rightarrow_(\lambda)^(+)q e q\to_(a)r. Neste caso, o vértice q, de modo geral, pode não pertencer ao conjunto Q ", ou seja, pode desaparecer ao passar para o autômato M" (Fig. 7.11). Mas se q\in Q" , então, naturalmente, o arco (q,r) será preservado em M" e o símbolo a será um dos símbolos pertencentes ao rótulo desse arco (Fig. 7.12).

Assim, em M" são armazenados todos os arcos M cujos rótulos são diferentes de \lambda e que conectam um par (vértices) de estados do conjunto Q" (não removido conforme item a). Além disso, para qualquer triplo de estados p,q,r (não necessariamente distintos!), tal que p,r\in Q" e existe um caminho de comprimento diferente de zero de p a q cujo rótulo é igual a \lambda (isto é, o caminho por transições λ), e de q a r um arco conduz, cujo rótulo contém o símbolo a do alfabeto de entrada, em M" um arco é construído de p a r, cujo rótulo contém o símbolo a (ver Fig. 7.11).

dentro. O conjunto de estados finais F" do autômato finito M" contém todos os estados q\in Q" , ou seja, os estados do autômato finito M que não são deletados de acordo com o item a, para os quais q\Rightarrow_(\lambda)^(\ast)q_f para algum q_f\in F (ou seja, o próprio estado q é o estado final do autômato finito M, ou a partir dele um caminho de comprimento diferente de zero ao longo dos arcos rotulados \lambda leva a um dos estados finais do autômato finito M ) (Fig. 7.13).

2. Na verdade, determinação.

Deixar M=(Q,V,q_0,F,\delta)é um autômato finito sem transições λ. Vamos construir um autômato finito determinístico equivalente M_1 .

Este autômato finito é definido de tal forma que seu conjunto de estados é o conjunto de todos os subconjuntos do conjunto de estados do autômato finito M . Isso significa que cada estado individual do autômato finito M_1 é definido como algum subconjunto do conjunto de estados do autômato finito M. Neste caso, o estado inicial do novo autômato finito (ou seja, M_1 ) é um subconjunto singleton contendo o estado inicial do antigo autômato finito (ou seja, M ), e os estados finais do novo autômato finito são todos esses subconjuntos Q que contêm pelo menos um final no topo do autômato finito original M .

Daqui em diante, permitindo alguma liberdade de expressão, às vezes chamaremos os estados do autômato finito M_1 de conjuntos de estados. É importante, no entanto, entender claramente que cada conjunto de estados é um estado separado do novo autômato finito, mas não um conjunto de seus estados. Ao mesmo tempo, para o autômato finito original ("antigo") M, este é precisamente o conjunto de seus estados. Falando figurativamente, cada subconjunto de estados do antigo autômato finito é "colapsado" em um estado do novo autômato finito*.

*Formalmente, o conjunto Q_1 deve ser definido como um conjunto que está em correspondência biunívoca com o conjunto 2^Q , mas ainda é mais conveniente considerarmos que Q_1 coincide com 2^Q , pois o conjunto de estados de um autômato finito pode ser qualquer conjunto finito não vazio.

A função de transição do novo autômato finito é definida de modo que do conjunto de estados S pelo símbolo de entrada a o autômato finito M_1 passa para o conjunto de estados, que é a união de todos os conjuntos de estados do antigo autômato finito, para que este velho autômato finito passa pelo símbolo a de cada conjunto de estados S . Assim, o autômato finito M_1 é determinístico por construção.

A descrição verbal acima pode ser traduzida em fórmulas da seguinte forma: construímos a máquina de estados M_1 para que

M_1=(Q_1,V,\(q_0\),F_1,\delta_1), Onde

\begin(cases)Q_1=2^Q,\quad F_1=\(T\colon\, T\cap F\ne\varnothing,~T\in2^Q\),\\ (\forall S\subseteq Q) (\forall a\in V)\Bigl(\delta_1(S,a)= \bigcup\limits_(q\in S)\delta(q,a)\Bigr). \end(casos)

Prestemos atenção ao fato de que entre os estados do novo autômato finito existe um estado \varnothing , e, de acordo com (7.8), \delta_1(\varnothing,a)=\varnothing para qualquer caractere de entrada a . Isso significa que, uma vez nesse estado, a máquina de estado M_1 não o deixará. Em geral, qualquer estado q de um autômato finito tal que para qualquer símbolo de entrada a tenhamos \delta(q,a)=q é chamado de estado absorvente do autômato finito. Assim, o estado \varnothing da máquina de estados determinística M_1 é absorvente. Também é útil notar que \delta_1(S,a)=\varnothing se e somente se para cada q\in S (estados do antigo autômato finito do conjunto de estados S ) \delta(q,a)=\varnothing, ou seja no grafo M, cada um desses estados q não deixa nenhum arco marcado com o símbolo a .

Pode-se provar que o autômato finito obtido por tal algoritmo é equivalente ao original.

Exemplo 7.9. Determinamos o autômato finito mostrado na Fig. 7.14.

Um autômato finito equivalente sem transições λ é mostrado na fig. 7.15. Observe que o vértice q_2 desaparece, pois apenas arcos "vazios" entram nele.

Para determinar o autômato resultante, não é absolutamente necessário escrever todos os seus 2^3=8 estados, muitos dos quais podem não ser alcançáveis ​​a partir do estado inicial \(q_0\) . Para obter os estados \(q_0\) alcançáveis, e apenas eles, usamos o chamado método pull.

Este método pode ser descrito no caso geral como segue.

No autômato finito original (sem arcos vazios), definimos todos os conjuntos de estados que são alcançáveis ​​a partir do inicial, ou seja, para cada caractere de entrada a encontramos o conjunto \delta(q_0,a) . Cada um desses conjuntos no novo autômato é um estado diretamente acessível a partir do inicial.

Para cada um dos conjuntos de estados definidos S e cada símbolo de entrada a, encontramos o conjunto \textstyle(\mathop(\bigcup\limits_(q\in S) \delta(q,a))\limits^(\phantom(A)^(.))). Todos os estados obtidos nesta etapa serão os estados de um novo autômato (determinístico), alcançável a partir do vértice inicial ao longo de um caminho de comprimento 2. Repetimos o procedimento descrito até que nenhum novo conjunto de estados (incluindo o vazio) apareça. Pode-se mostrar que neste caso são obtidos todos os estados do autômato finito M_1 que são alcançáveis ​​a partir do estado inicial \(q_0\) .

Para a máquina de estados finitos da Fig. 7.15 temos:

\begin(alinhado)& \delta_1(\(q_0\),a)=\(q_1\);\qquad \delta_1(\(q_0\),b)=\(q_1,q_3\);\\ & \ delta_1(\(q_1\),a)=\(q_1\);\qquad \delta_1(\(q_1\),b)=\(q_1\);\\ & \delta_1(\(q_1,q_3\) ,a)= \delta(q_1,a)\cup \delta(q_3,a)= \(q_1\)\cup\(q_1\)=\(q_1\);\\ & \delta_1(\(q_1, q_3\),b)= \delta(q_1,b)\cup \delta(q_3,b)= \(q_1\)\cup\(q_1\)=\(q_1\). \end(alinhado)

Como não há mais novos conjuntos de estados, o procedimento de "puxar" termina aqui e obtemos o gráfico mostrado na Fig. 7.16.

Complemento de Linguagem Regular

Uma das consequências teóricas importantes do teorema da determinização é o seguinte teorema.

Teorema 7.8. O complemento de uma linguagem regular é uma linguagem regular.

Seja L uma linguagem regular no alfabeto V . Então o complemento da linguagem L (como um conjunto de palavras) é a linguagem \overline(L)=V^(\ast)\setminus L.

De acordo com o Teorema 7.7, para uma linguagem regular L, um autômato finito determinístico M pode ser construído que admite L . Como em um autômato determinístico de cada vértice, para cada símbolo de entrada, é definida uma transição para exatamente um vértice, então, qualquer que seja a string x no alfabeto V , existe um caminho único para ela em M, começando na inicial estado no qual a string x é lida. É claro que a string x é permitida pelo autômato M , ou seja, x\in L(M) , se e somente se o último estado do caminho especificado for final. Isso implica que a cadeia x\notin L(M) se e somente se o último estado do caminho especificado não for final. Mas precisamos apenas de um autômato finito M" , que permite a cadeia x se e somente se o autômato finito original M não permite. .

O teorema provado nos permite construir um autômato finito que não permite um determinado conjunto de cadeias pelo seguinte método: primeiro, construímos um autômato que permite um determinado conjunto de cadeias, depois o determinamos e passamos ao autômato para o complemento como indicado na prova do Teorema 7.8.

Exemplo 7.10. uma. Vamos construir um autômato finito que permita todas as strings do alfabeto \(0;1\), exceto a string 101.

Primeiro, construímos um autômato finito que permite uma única cadeia 101. Este autômato é mostrado na fig. 7.17.

Este autômato é quase determinístico, mas não determinístico, pois não está totalmente definido. Vamos determiná-lo e obter um autômato finito equivalente determinístico mostrado na Fig. 7.18.

E finalmente, passando para a adição (e renomeando os estados), obtemos o autômato mostrado na Fig. 7.19.

Observe que no autômato resultante, todos os vértices, exceto o vértice s_3 , são finais.

Observe também que a transição para o complemento, que é discutida na prova do Teorema 7.8, só pode ser realizada em um autômato determinístico. Se invertermos os papéis dos vértices finais e não finais no autômato mostrado na Fig. 7.17, obteríamos um autômato que admite a linguagem \(\lambda,1,10\) , que não é - como é fácil ver - o conjunto de todas as strings exceto a string 101.

Observe também que a máquina de estados finitos da Fig. 7.19 permite todas as strings que contêm uma ocorrência da string 101, mas não correspondem à string em si. Aqui, por exemplo, está o caminho que carrega a cadeia 1011: s_0,s_1,s_2,s_3,t.

b. Vamos construir um autômato finito que permita todas as strings do alfabeto \(0;1\) , exceto aquelas que contêm uma ocorrência da string 101. Considere uma linguagem L , cada string contendo uma ocorrência da string 101. Ele pode ser definido da seguinte forma:

L=(0+1)^(\ast)101(0+1)^(\ast).

Precisamos construir um autômato para complementar a linguagem L.

Diretamente da expressão regular neste caso, é fácil construir um autômato finito que permite a linguagem L (Fig. 7.20).

Em seguida, pelo método "puxar", realizaremos a determinação. O resultado da determinação mostra-se no figo. 7.21.

Para uma solução completa do problema, apenas a Fig. 7.21 troque os papéis dos vértices final e não final (Fig. 7.22).

dentro. Vamos discutir a ideia de construir um autômato finito que permita aquelas e somente aquelas strings do alfabeto \(0;1\) que não começam com a string 01 e não terminam com a string 11 (ou seja, strings do form 01x e strings no formato y11 não são permitidas, quaisquer que sejam as chains x,y\in\(0;1\) ).

Nesse caso, o complemento da linguagem para a qual é necessário construir um autômato finito é o conjunto de todas essas cadeias de zeros e uns que começam com a cadeia 01 ou terminam com a cadeia 11. Um autômato que admite esse conjunto de strings é construído como um autômato para combinar 01(0+1)^(\ast)+(0+1)^(\ast)11 da mesma forma que na prova do teorema de Kleene (ver Teorema 7.6).

A propriedade da classe de linguagens regulares ser fechada sob complemento (ver Teorema 7.8) imediatamente implica que esta classe é fechada sob diferenças de interseção, teoria de conjuntos e simétricas.

Corolário 7.3. Para quaisquer duas linguagens regulares L_1 e L_2, as seguintes afirmações são verdadeiras:

1) a interseção L_1\cap L_2 é regular;
2) a diferença L_1\setminus L_2 é regular;
3) diferença simétrica L_1\vartriângulo L_2 regular.

A validade das declarações decorre das identidades:

\begin(aligned) &(\scriptstyle(\mathsf(1))))\quad L_1\cap L_2= \overline(\overline(L_1) \cup\overline(L_2))\,;\\ &(\scriptstyle (\mathsf(2))))\quad L_1\setminus L_2= L_1\cap \overline(L_2)\,;\\ &(\scriptstyle(\mathsf(3))))\quad L_1\,\triangle\ ,L_2 = (L_1\cup L_2)\setminus (L_1\cap L_2).\end(alinhado)

Primeiramente, os resultados obtidos permitem afirmar que a classe das linguagens regulares no que diz respeito às operações de união, interseção e adição é uma álgebra booleana, em que a unidade é a linguagem universal, e o zero é a linguagem vazia . Em segundo lugar, essas propriedades algébricas da família das linguagens regulares nos permitem resolver o importante problema de reconhecer a equivalência de dois autômatos finitos arbitrários.

De acordo com a Definição 7.10, autômatos finitos são equivalentes se as linguagens que eles permitem são as mesmas. Portanto, para verificar a equivalência dos autômatos M_1 e M_2, basta provar que a diferença simétrica das linguagens L(M_1) e L(M_2) é vazia. Para isso, por sua vez, basta construir um autômato que admita essa diferença e verificar se a linguagem que ele admite é vazia. Em geral, o problema de reconhecer que uma linguagem de máquina de estado está vazia é chamado de problema de vazio de máquina de estado. Para resolver este problema, basta encontrar o conjunto de estados finais do autômato que são alcançáveis ​​a partir do estado inicial. Como a máquina de estados finitos é um grafo direcionado, esse problema pode ser resolvido, por exemplo, usando busca em largura. A linguagem permitida pelo autômato finito é vazia se e somente se o conjunto de estados finais alcançáveis ​​a partir do estado inicial for vazio. Na prática, é preferível reconhecer a equivalência de autômatos finitos usando um algoritmo de minimização, mas agora é importante enfatizarmos que a possibilidade fundamental de resolver o problema de equivalência decorre do Teorema 7.7 e suas consequências algébricas.