3 апреля, 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
(т. е. Перечисление — это один элемент, либо перечисление + точка с запятой + элемент).
В javacc правило будет таким:
Enumeration -> (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;} } </literal></number></semicolon></node></node></node></cbra></obra></node></eof></semicolon:></cbra:></obra:></literal:></number> |
Для того, чтоб использовать полиморфизм при построении дерева, я создал интерфейс:
//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); } </node></node> |
От него унаследован базовый класс:
//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){ } } </node></node> |
От него унаследованы три класса для описания конкретных типов вершин:
//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; } } </node></node></enumnode></node> |
Класс для тестирования парсера:
//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 
Tags: