UCFS

UCFS

• Sobre
• Uso
  • De fontes
  • Usando jar
  • Exemplo de formato CFG
  • Exemplo de formato RSM
• Desempenho
  • Gráficos
  • Gramáticas
  • Resultados
  • Mais resultados

Nota: Projeto sob desenvolvimento pesado!

Sobre

O UCFS é um cenário nuversal : uma ferramenta para resolver problemas relacionados à interseção de idiomas regular e livre de contexto. Exemplos de tais problemas:

• Análise
• Consulta de caminho sem contexto (CFPQ)
• A alcance da linguagem sem contexto (CFL-R)

Uso

Interface da linha de comando

 Usage: kotgll options_list
Options: 
    --input -> Input format (always required) { Value should be one of [string, graph] }
    --grammar -> Grammar format (always required) { Value should be one of [cfg, rsm] }
    --sppf [ON] -> Sppf mode { Value should be one of [on, off] }
    --inputPath -> Path to input txt file (always required) { String }
    --grammarPath -> Path to grammar txt file (always required) { String }
    --outputPath -> Path to output txt file (always required) { String }
    --help, -h -> Usage info

De fontes

Etapa 1. Repositório de clone

git clone https://github.com/FormalLanguageConstrainedPathQuerying/kotgll.git

ou

git clone [email protected]:FormalLanguageConstrainedPathQuerying/kotgll.git

ou

gh repo clone FormalLanguageConstrainedPathQuerying/kotgll

Etapa 2. Vá para a pasta

cd kotgll

Etapa 3. Execute o comando de ajuda

gradle run --args="--help"

Você verá a mensagem "Lista de opções".

Exemplo

 gradle run --args="--input graph --grammar rsm --sppf off --inputPath src/test/resources/cli/TestGraphReadWriteCSV/dyck.csv --grammarPath src/test/resources/cli/TestRSMReadWriteTXT/dyck.txt --outputPath ./result.txt"

Usando jar

Etapa 1. Faça o download do frasco mais recente

 curl -L -O https://github.com/FormalLanguageConstrainedPathQuerying/kotgll/releases/download/v1.0.0/kotgll-1.0.0.jar

Etapa 2. Execute jar com java

 java -jar kotgll-1.0.0.jar --input graph --grammar rsm --sppf off --inputPath src/test/resources/cli/TestGraphReadWriteCSV/dyck.csv --grammarPath src/test/resources/cli/TestRSMReadWriteTXT/dyck.txt --outputPath ./result.txt

Exemplo de formato CFG

 StartNonterminal("S")
Nonterminal("S") -> Terminal("subClassOf_r") Nonterminal("S") Terminal("subClassOf")
Nonterminal("S") -> Terminal("subClassOf_r") Terminal("subClassOf")
Nonterminal("S") -> Terminal("type_r") Nonterminal("S") Terminal("type")
Nonterminal("S") -> Terminal("type_r") Terminal("type")

Exemplo de formato RSM

 StartState(id=0,nonterminal=Nonterminal("S"),isStart=true,isFinal=false)
State(id=0,nonterminal=Nonterminal("S"),isStart=true,isFinal=false)
State(id=1,nonterminal=Nonterminal("S"),isStart=false,isFinal=false)
State(id=4,nonterminal=Nonterminal("S"),isStart=false,isFinal=false)
State(id=3,nonterminal=Nonterminal("S"),isStart=false,isFinal=true)
State(id=2,nonterminal=Nonterminal("S"),isStart=false,isFinal=false)
State(id=6,nonterminal=Nonterminal("S"),isStart=false,isFinal=true)
State(id=5,nonterminal=Nonterminal("S"),isStart=false,isFinal=false)
TerminalEdge(tail=0,head=1,terminal=Terminal("subClassOf_r"))
TerminalEdge(tail=0,head=4,terminal=Terminal("type_r"))
TerminalEdge(tail=1,head=3,terminal=Terminal("subClassOf"))
NonterminalEdge(tail=1,head=2,nonterminal=Nonterminal("S"))
TerminalEdge(tail=4,head=6,terminal=Terminal("type"))
NonterminalEdge(tail=4,head=5,nonterminal=Nonterminal("S"))
TerminalEdge(tail=2,head=3,terminal=Terminal("subClassOf"))
TerminalEdge(tail=5,head=6,terminal=Terminal("type"))

Desempenho

O algoritmo GLL foi modificado para suportar a entrada gráfica. A modificação proposta foi avaliada em vários gráficos reais para o cenário de encontrar todos os pares de acessibilidade.

Configuração da máquina : PC com Ubuntu 20.04, Intel Core i7-6700 3,40GHz CPU, DDR4 64GB RAM.

Configuração enxinada :

• Java Hotspot (TM) Máquina virtual de servidor de 64 bits (construir 15.0.2+7-27, modo misto, compartilhamento).
• Configuração do Heap JVM: 55 GB tanto XMS e XMX.

Gráficos

Os dados do gráfico são selecionados no conjunto de dados CFPQ_DATA.

Uma descrição detalhada dos gráficos está listada abaixo.

Gráficos de análise RDF

Nome do gráfico	| V |	| E |	#subclassof	#tipo	#BroaderTransitive
Enzima	48 815	86 543	8 163	14 989	8 156
Eclass	239 111	360 248	90 962	72 517	0
Hierarquia	45 007	490 109	490 109	0	0
Ir	582 929	1 437 437	94 514	226 481	0
GeoSpécies	450 609	2 201 532	0	89 065	20 867
Taxonomia	5 728 398	14 922 125	2 112 637	2 508 635	0

Gramáticas

Todas as consultas usadas na avaliação são variantes de consulta de mesma geração. O inverso de uma relação x e a respectiva borda é indicada como x_r .

Gramáticas usadas para gráficos RDF :

G ₁

 S -> subClassOf_r S subClassOf | subClassOf_r subClassOf 
     | type_r S type | type_r type

A representação da gramática G ₁ sem contexto no repositório pode ser encontrada aqui.

A representação da gramática G ₁ sem contexto como autômato recursivo no repositório pode ser encontrado aqui.

Resultados

Os resultados da avaliação de consultas de alcance de todos os pares em gráficos relacionados à análise RDF estão listados abaixo.

Em cada linha, o melhor tempo em tempo em segundos é destacado em negrito .

Gráfico	Cfg	RSM	Gll4graph
Enzima	0,107	0,044	0,22
Eclass	0,94	0,43	1.5
Hierarquia	4.1	3.0	3.6
Ir	3.2	1.86	5.55
GeoSpécies	0,97	0,34	2.89
Taxonomia	31.2	14.8	45.4

Mais resultados

Mais resultados, mas em forma bruta, podem ser encontrados no repositório kotgll_benchmarks