
Продолжаем создавать парсеры на 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 |
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
} |
{
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;}
}
</literal></number></semicolon></node></node></node></cbra></obra></node></eof></semicolon:></cbra:></obra:></literal:></number> |
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;
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;
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 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;
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.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() ;
}
}
} |
//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 |
[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
В первой части выводить наглядно с помощью отступов структуру перечисления. После черточек выводим рекурсивно перемешанные значения элементов каждого перечисления.