Unfuzzying fuzzy parsing

Abstract

Recognizing sentences of a language in an efficient and precise manner has always been a strong subject within computer science. Many theories, algorithms and techniques have been proposed along computing history, but at the end it all comes down to performing lexical and syntactic analysis of the source, originating a parse tree as the result. Sometimes there is no need for full precision or even a full parse tree. A good example of one of these cases is architecture extraction from source code. In this case only a small portion of the code is of interest. Another good example is recognizing handwritten expressions, because it is entirely impossible to predict the kind of calligraphy that will be analyzed, it is also impossible to perform an one hundred percent precise recognition. This need for tolerant parsing lead to the development of many forms of tolerant parsing along the years. This master work will focus on one form of tolerant parsing in particular, Fuzzy Parsing. From this work it is expected the emergence of a new Fuzzy Parsing technique based on automata, where automata states would represent context and edges would represent potential matches inside that context. The hypothesis of this work is that such an approach reduces uncertainty and recognition time. It is also expected the creation of a tool suit that facilitates the process of developing fuzzy parsers. We believe that such a tool will be a great addition to areas such as Program Comprehension or IDE construction.

Reconhecer frases de uma linguagem, de uma forma eficiente e precisa, tem sido sempre um tópico de interesse dentro da Informática. Diversas teorias, algoritmos e técnicas foram propostas ao longo dos anos, mas no fim de contas tudo se baseia em análises léxicas, sintáticas e semânticas da fonte, originando uma árvore de parsing como resultado. Por vezes não há necessidade de um reconhecimento cem por cento preciso, nem de uma árvore de parsing completa. Um bom exemplo de um desses casos, pode ser encontrado na extração de modelos arquiteturais a partir de código fonte. Neste caso, apenas uma parte reduzida do código tem interesse. Outro bom exemplo pode ser encontrado no reconhecimento de expressões matemáticas escritas manualmente. Uma vez que é impossível prever o tipo de caligrafia a ser analisada, é também impossível realizar um reconhecimento cem por cento preciso. Esta necessidade por tolerância no reconhecimento levou ao desenvolvimento de várias técnicas de parsing tolerante ao longo dos anos. Esta dissertação irá focar-se particularmente numa forma de parsing tolerante, Fuzzy Parsing. Deste trabalho é esperado que surja uma nova técnica de Fuzzy Parsing baseada em autómatos, onde os estados representarão contexto e os arcos representarão possíveis correspondências dentro desse contexto. Espera-se que esta abordagem reduza a incerteza e o tempo de reconhecimento. É também esperado que seja criada uma ferramenta que facilite o processo de criação de outros fuzzy parsers. Pensamos que uma ferramenta do género será uma bela adição ao para áreas como análise de programas e construção de ambientes de desenvolvimento de software.