Abstract | ||
---|---|---|
In this paper a platform is presented, that given a stochastic context-free grammar (SCFG), automatically outputs the description of the parser in synthesizable hardware description language (HDL) which can be downloaded in an Field Programmable Gate Arrays (FPGA) board. Initially, according to our methodology the SCFG is augmented with attributes which store the probability values and can be evaluated through corresponding stack actions. The architecture of the produced system is based on a proposed extension of Earley's parallel algorithm, which given an input string, generates the parse trees in the form of an AND-Or parse tree. This AND- or parse tree is then traversed using a proposed tree traversal technique in order to execute the corresponding actions in the correct order, so as to compute the necessary probabilities. The platform is suitable for embedded systems applications where a natural language interface is required or in pattern recognition tasks. The parser generated by the presented platform has been tested for various SCFGs and compared to software approaches. The performance comparison is one to two orders of magnitude in favor of the presented hardware, compared to previous software approaches, depending on the application, the input string length and the number of produced trees. |
Year | DOI | Venue |
---|---|---|
2016 | 10.1142/S0218001416500087 | INTERNATIONAL JOURNAL OF PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE |
Keywords | Field | DocType |
Stochastic context-free grammars, parsers, hardware, FPGA, design automation | Programming language,Parse tree,Tree traversal,LR parser,Parallel algorithm,Computer science,Field-programmable gate array,Synchronous context-free grammar,Artificial intelligence,Parsing,Machine learning,Hardware description language | Journal |
Volume | Issue | ISSN |
30 | 4 | 0218-0014 |
Citations | PageRank | References |
2 | 0.38 | 19 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Christos Pavlatos | 1 | 16 | 4.74 |
Alexandros C. Dimopoulos | 2 | 23 | 5.50 |
George K. Papakonstantinou | 3 | 159 | 61.88 |