Разбор рекурсивной грамматики с помощью javacc

Апрель 3rd, 2015 rius

Продолжаем создавать парсеры на java с помощью javacc. В этот раз рассмотрим разбор грамматики, которую уже разбирали с помощью lex+yacc тут: ссылка. В той статье есть BNF для данного языка в понятном для yacc виде.

Для простоты я опять закомментировал название пакета — если надо, раскоментируйте и ставьте свой.

Я собирал с помощью make:

JAVACC_JAR = /home/dk/javacc_6_1/javacc-6.1.0/target/javacc-6.1.0.jar
SOURCE_NAME=enumParser
 
all: ParserDemoTest.java EnumParser.java
	javac *.java	 
 
EnumParser.java : $(SOURCE_NAME).jj
	java -cp $(JAVACC_JAR) javacc $(SOURCE_NAME).jj
 
clean: 
	rm -rf ./ParseException.*
	rm -rf ./SimpleCharStream.*
	rm -rf ./EnumParser.*
	rm -rf ./EnumParserConstants.*
	rm -rf ./EnumParserTokenManager.*
	rm -rf ./Token.*
	rm -rf ./TokenMgrError.*
	rm -rf ./*.class

Если все исходники лежат в текущей папке, то название пакета не нужно.

Разбирать будем конструкции вида:

{
    11111; asdgf;
    {
        222; 4444;
        {
           88888; {YYYYY}
        };
        33333
    }
    ;
     ttttt 
}

Т.е. это перечисления, элементами которых могут быть строки, числа и другие перечисления. Разделитель — точка с запятой.

При создании объекта парсера надо предоставить какой-нибудь Reader, но это необязательно FileReader. В этот раз для разнообразия будем парсить сразу строку с помощью StringReader.

У обработки рекурсии в javacc есть тонкость: javacc вообще не понимает левую рекурсию.
Это означает, что не получится задать правило в виде:
Enumeration -> Enumeration Element | Element
(т. е. Перечисление — это один элемент, либо перечисление + точка с запятой + элемент).
В javacc правило будет таким:
Enumeration -> (Element )* Element
(перечисление — это один элемент и возможно любое число пар [элемент + точка с запятой перед ним]).
Придумывать свою логику для построения связного списка необязательно, уже придуман удобный класс ArrayList.

Полное содержание файла enumparser.jj:

options
{
    STATIC = false;
}
PARSER_BEGIN (EnumParser)
   //package ru.outofrange.javacc.enumparser;
   import java.util.ArrayList;
   import java.util.List;
   import java.util.HashMap;
 
   class EnumParser {
         Node initParser() throws ParseException, TokenMgrError { 
             return(init()) ; 
         //private Node root;
         }
   }
PARSER_END (EnumParser)
 
SKIP: { "\n" | "\r" | "\r\n" | "\\" | "\t" | " "}
 
TOKEN [IGNORE_CASE]:
{
 <number :(["0"-"9"])+ >
|<literal: (["a"-"z"])+ >
|<obra: ("{")+>
|<cbra: ("}")+>
|<semicolon: (";")>
}
 
Node init():
{
  Node node;
  Token T;
}
{
  (
       node = Statement()
  )
  <eof>
  {
     return node; // root of the tree here
  }
}
 
Node Statement():
{
   List<node> content;
   Node node;
}
{
  (    
       <obra>
       content = Enumeration()
       <cbra>
  )
  { 
    //System.out.println("Statement found");
    node = new EnumNode();
 
    node.setContent(content);
    return node;
  }
}
 
List<Node> Enumeration():
{
    Node node = null;
    List<Node> content = new ArrayList<Node>();
}
{
  (
    (  LOOKAHEAD(2222)
       node = Element() <semicolon>
       {  
          //System.out.println("[Recursion] Element found " + node);
          content.add(node);
       }
    )*
    node = Element()
    {
      //System.out.println("Element found " + node);
      content.add(node);
    }
  )
  {
     return content;
  }
}
 
Node Element():
{
   Token t;
   Node node;
}
{
  (
     t=<number>
     { 
        node = new NumberNode(); 
        node.setValue(t.image); 
        //System.out.println("Number node found < " + node + ">");
     }
     |
     t=<literal>
     { 
        node = new TextNode(); 
        node.setValue(t.image); 
        //System.out.println("Text node found < " + node + ">");
     }
     |
     node=Statement()
  )
  {return node;}
}

Для того, чтоб использовать полиморфизм при построении дерева, я создал интерфейс:

//package ru.outofrange.javacc.enumparser;
 
import java.util.List;
 
public interface Node {
 
	public List<Node> getContent();
	public void setContent(List<Node> nodeList);
	public void setValue(String value);
}

От него унаследован базовый класс:

//package ru.outofrange.javacc.enumparser;
 
import java.util.List;
 
//package ru.outofrange.javacc.enumparser;
 
import java.util.List;
 
public class BasisNode implements Node {
 
        // will return non null only for EnumNode:
        public List<Node> getContent(){
		return null;
        }
 
        public void setContent(List<Node> cont){
	}
 
        public void setValue(String value){
	}
 
}

От него унаследованы три класса для описания конкретных типов вершин:

//package ru.outofrange.javacc.enumparser;
 
public class TextNode extends BasisNode {
 
        private String value;
 
        public void setValue(String val){
            this.value = val;
        }
 
        public String getValue(){
            return value;
        }
 
        public String toString(){
		return value;
	}
 
}
//package ru.outofrange.javacc.enumparser;
 
public class NumberNode extends BasisNode {
 
        private Integer value;
 
        public NumberNode() {
        }
 
        public void setValue(String val){
            this.value = Integer.valueOf(val);
        }
 
        public void setValue(Integer val){
            this.value = value;
        }
 
        public Integer getValue(){
            return value;
        }
 
        public String toString(){
	    return String.valueOf(value);
	}
 
}
//package ru.outofrange.javacc.enumparser;
import java.util.List;
 
public class EnumNode extends BasisNode {
 
        private List<Node> content = null;
 
        public String toString(){
		return "<enumnode>";
        }
 
        public void setContent(List<node> cont){
		content = cont;
        }
 
        public List<Node> getContent(){
		return content;
        }
 
}

Класс для тестирования парсера:

//package ru.outofrange.javacc.enumparser;
 
import java.io.StringReader;
import java.util.ArrayList;
import java.util.Random;
 
public class ParserDemoTest { 
 
    public static final String DELIMITER = ", ";
 
    public static void printOut (Node node, int level){
        if (node != null) {
            //int internalLevel = level;
            if (node.getContent() != null){
                for (Node nestedNode: node.getContent()){
                    // indents
 
                    printOut(nestedNode, level + 1);
                }
            } else {
                for (int i = 0; i < level - 1; i++){
                    System.out.print("    ");
                }   
                System.out.println(node);
            }
        }
    }
 
    // prints elements of each enumeration in random order recursively
    public static String printStringValues (Node node){
 
        StringBuffer res = new StringBuffer();
 
        if (node != null) {
 
            if (node.getContent() != null){ // it's an enumeration
 
                Random randomGenerator = new Random();
 
                for (Node nestedNode: node.getContent()){
 
                    // deciding if we prepend or append
                    int i = randomGenerator.nextInt(2);
 
                    if (i == 1) { // appending
                        if (res.length() > 0) {
                            res.append (DELIMITER);
                        }
                        res.append ( printStringValues(nestedNode));   
                    } else { // prepending
 
                        if (res.length() > 0) {
                            res.insert(0, printStringValues(nestedNode) + DELIMITER);
                        } else {
                            res.insert(0, printStringValues(nestedNode));
                        }
                    }
 
                }
            } else { // it's not an enumeration
                return node.toString();
            }
        }
 
        return res.toString();
    }
 
    public static void main(String[] args) { 
        try{ 
            if (args.length < 1) {
                return;
            }
            String str = args[0];
 
            EnumParser parser = new EnumParser (new StringReader(str)); 
            Node root = parser.initParser();
 
            printOut (root, 0);
 
            System.out.println(" -------------------------");
 
            System.out.println(printStringValues(root));
 
        } catch (Exception ex) {
            ex.printStackTrace() ;
        } 
    } 
}

В этом классе две рекурсивные функции. Первая выводит описание перечисления с отступами. Вторая перемешивает элементы.

Результат выполнения программы:

[root@dmitry JAVACC_nested]# java ParserDemoTest "{ 11111; asdgf; { 222; 4444; {  88888; {YYYYY} };  33333 } ; ttttt }"
11111
asdgf
    222
    4444
        88888
            YYYYY
    33333
ttttt
 -------------------------
222, 4444, 88888, YYYYY, 33333, asdgf, 11111, ttttt
 
[root@dmitry JAVACC_nested]# java ParserDemoTest "{ 11111; asdgf; { 222; 4444; {  88888; {YYYYY} };  33333 } ; ttttt }"
11111
asdgf
    222
    4444
        88888
            YYYYY
    33333
ttttt
 -------------------------
ttttt, 33333, 88888, YYYYY, 222, 4444, 11111, asdgf

В первой части выводить наглядно с помощью отступов структуру перечисления. После черточек выводим рекурсивно перемешанные значения элементов каждого перечисления.

Posted in Linux, Программирование Tags: ,
«
»
You can leave a response, or trackback from your own site.

Leave a Reply