Gramatica Livre de Contexto

Programação Java
#1

oi gente tudo bem?

Alguem já trabalhou implementando gramáticas livre de contexto.

Tipo, preciso de saber qual é a melhor estrutura de dados para representar as regras de derivação.

Ex:

S -> NP VP 1.0
VP -> Vt NP 0.8
VP -> VP PP 0.2

tipo eu tenho um não terminal que vai para 2 outros em uma determinada probabilidade.

Antes que alguem comece a zuar. eu não quero o trabalho resolvido. quero sugestões a respeito da estrutura de dados para representar isso.

Atenciosamente.

#2

Estrutura de dados para gramática? Nunca ouvi falar algo do tipo. O que você pode ter são algoritmos para reconhecer linguagens que obedeçam as regras gerativas da gramática. Quem faz essas coisas são os parsers (analisadores sintáticos). Qual é exatamente seu problema? Você quer verificar se determinada String está contida em uma linguagem?

#3

Eu preciso implementar algoritmos que trabalham com gramáticas livre de contexto como CKY por exemplo e então preciso saber representar GLC aqui. Por exemplo, G = (N,Sig,R,S).
N= não terminais.
Sig = terminais.
R = Regras.
S = estado inicial.

depois vou trabalhar com parsing de linguagem natural. gostaria de saber como é usual representar gramáticas em java. A principio to criando um monte de classes.

#4

Conheço a teoria, não precisa explicar :wink:
Na verdade a definição formal de uma GLC não é bem assim, mas tudo bem, isso não vem ao caso agora.
Você pode usar o ANTLR para gerar seu parser. http://www.antlr4.org/
Deixa eu ver se sai alguma coisa aqui… Estou com um pouco de sono…

#5

Segue um exemplo muito bobo de uma gramática do ANTLR, composto por uma regra (identificador) e dois tokens (LETRA e DIGITO).

[code]grammar Teste;

identificador : LETRA (LETRA | DIGITO)* EOF;
LETRA : ‘a’…‘z’ | ‘A’…‘Z’;
DIGITO : ‘0’…‘9’;[/code]

Usando o ANTLRWorks vc vai escrever sua gramática, preenchê-la com o código Java que você quer que seja executado durante o parse e gerar o parser e o lexer para usar no seu programa. Já te adianto que você vai ter que ler o livro do Terence Parr (pai do ANTLR) para poder usar o gerador satisfatoriamente.

[]'s

#6