第 4 回 文脈自由文法と構文解析木

private boolean A(){
   if(記号 b を認識できたら){
     次の文字を読み込む
     if(C()){
       if(D()){
         return true;
       }
     }
   }
   return false;
}

def A():
    if 記号 b を認識できたら:
        次の文字を読み込む
        if C():
            if D():
                return True
    return False

import java.io.*;
class Parser {
    public Parser(Reader r){
	reader = new BufferedReader(r);
    }
    final private BufferedReader reader;
    public boolean S() throws IOException{
	if(A() || B()){ // A がだめなら B
	    return true;
	}else{
	    return false;
	}
    }
    private boolean A() throws IOException{
	reader.mark(2); // 2 文字読んだあと戻す可能性がある
        if(reader.read()=='a' && reader.read()=='b'){
          return true;
        }
        reader.reset();
	return false;
    }
    private boolean B() throws IOException{
	reader.mark(2);
        if(reader.read()=='a' && reader.read()=='c'){
          return true;
        }
        reader.reset();
	return false;
    }
}
class Rei {
    public static void main(String[] arg) throws IOException{
	Parser parser = new Parser(new InputStreamReader(System.in));
	if(parser.S()){
	    System.out.println("Ok");
	}else{
	    System.out.println("NG");
	}
    }
}

class Parser:
    def __init__(self, string):
        self.list= list(string)
        self.pointer = 0
    def __iter__(self):
        return self
    def __next__(self):
        if self.pointer >= len(self.list):
            raise StopIteration()
        result = self.list[self.pointer]
        self.pointer += 1
        return result
    def mark(self):
        self.m = self.pointer
    def reset(self):
        self.pointer = self.m
def S():
    if A() or B():
        return True
    else:
        return False
def A():
    reader.mark()
    if next(reader)=='a' and next(reader)=='b':
        return True
    reader.reset()
    return False
def B():
    reader.mark()
    if next(reader)=='a' and next(reader)=='c':
        return True
    reader.reset()
    return False;

reader = Parser(input())
if S():
    print("Ok")
else:
    print("NG")

private boolean A(){
  if(文字∈Director(A,α)){
    return αの処理が成功したか;
  }else if(文字∈Director(A,β)){
    return βの処理が成功したか;
  }...

  return false;
}

def A():
    if 文字∈Director(A,α):
        return αの処理が成功したか
    elif 文字∈Director(A,β):
        return βの処理が成功したか
    ...
    return False
}

private static boolean 始(){
   if(次 == 数){ // Director(始,和=)={数}
      if(和()){
        if(次 == '='){
          return true;
        }
      }
   }
   return false;
}
private static boolean 和(){
   if(次==数){ // Director(和,数和')={数}
      次を読む;
      if(和'()){
        return true;
      }
   }
   return false;
}
private static boolean 和'(){
   if(次=='='){ // Director(和',ε)
     return true;
   }else if(次=='+'){ // Director(和',+数和')
     次を読む;
     if(次==数){
       次を読む;
       if(和'()){
         return true;
       }
     }
   }
   return false;
}  
public static void main(String[] arg){
  次を読む;
  if(始()){
    System.out.println("Ok");
  }else{
    System.out.println("NG");
  }
}

def 始():
    if 次 == 数: # Director(始,和=)={数}
        if 和():
            if 次 == '=':
                return True
   return False

def 和():
    if 次==数: # Director(和,数和')={数}
        次を読む
        if 和'():
            return True
   return False

def 和'():
    if 次=='=': # Director(和',ε)
        return True
    elif 次=='+': # Director(和',+数和')
        次を読む
        if 次==数: 
            次を読む
            if 和'():
                return True
    return False

次を読む;
if 始():
    print("Ok")
else:
    print("NG")

import java.io.*;
class Parser {
    final private Reader reader;
    public Parser(Reader r) throws IOException{
	reader = r;
	c = reader.read();
    }
    private int c;
    public boolean s() throws IOException{
	System.err.println("called s.");
	if(Character.isDigit(c)){
	    if(wa1()){
		if(c=='='){
		    c = reader.read();
		    return true;
		}
	    }
	}
	return false;
    }
    private boolean wa1() throws IOException{
	System.err.println("called wa1.");
	if(Character.isDigit(c)){
	    c = reader.read();
	    if(wa2()){
		return true;
	    }
	}
	return false;
    }
    private boolean wa2() throws IOException{
	System.err.println("called wa2.");
	if(c=='='){
	    return true;
	}
	if(c=='+'){
	    c = reader.read();
	    if(Character.isDigit(c)){
		// 足し算の処理
		c = reader.read();
		if(wa2()){
		    return true;
		}
	    }
	}
	return false;
    }
}
class Rei {
    public static void main(String[] arg) throws IOException{
	final Reader r = new InputStreamReader(System.in);
	final Parser parser = new Parser(r);
	if(parser.s()){
	    System.out.println("accept");
	}else{
	    System.out.println("reject");
	}
    }
}

class Reader:
    def __init__(self, string):
        self.l = list(string)
        self.p = 0

    def read(self):
        if self.p >= len(self.l):
            raise StopIteration()
        result = self.l[self.p]
        self.p += 1
        return result
        
class Parser:
    def __init__(self, r):
        self.reader = r
        self.c = self.reader.read()
    def s(self):
        print("called s.")
        if self.c.isdecimal():
            if self.wa1():
                if self.c=='=':
                    return True
        return False
    def wa1(self):
        print("called wa1.")
        if self.c.isdecimal():
            self.c = self.reader.read()
            if self.wa2():
                return True
        return False

    def wa2(self):
        print("called wa2.")
        if self.c=='=':
            return True
        if self.c=='+':
            self.c = self.reader.read()
            if self.c.isdecimal():
		# 足し算の処理
                self.c = self.reader.read()
                if self.wa2():
                    return True
        return False

r = Reader(input())
parser = Parser(r)
if parser.s():
    print("accept")
else:
    print("reject")

public static void main(String[] arg){
  前処理;
  while(文字を読みつづける){ // 読み込みは一ヶ所
    文字列の組み立て処理;
    文字列が完成したら出力;
  }
  後処理;
}

前処理
for 文字 in list(文字列):
    文字列の組み立て処理
    文字列が完成したら出力
後処理

class Parser { 
  private boolean 非終端記号1(){
    if(トークン∈Director(非終端記号1,α)){
       return α の処理;
    }else if(文字∈Director(非終端記号1,β)){
       return β の処理;
    }...
    return false;
  }
  private boolean 非終端記号2(){
    トークンの列に応じて他の非終端記号を呼び出す;
    return true;
  }
...
}
/*
  α や β の処理中で文字を読み、終了判定も考慮される。
*/

class Rei {
  public static void main(String[] arg){
     if(開始記号()){
       System.out.println("受理");
     }else{
       System.out.println("拒否");
     }
  }
}

class Parser:
    def 非終端記号1(self):
        if トークン in Director(非終端記号1,α):
            return α の処理
        elif 文字 in Director(非終端記号1,β):
            return β の処理
        ...
        return False
    def 非終端記号2(self):
        トークンの列に応じて他の非終端記号を呼び出す
        return True
...

# α や β の処理中で文字を読み、終了判定も考慮される。

if 開始記号():
    print("受理")
else:
    print("拒否")

class Node {
}
class Kazu extends Node {
    private int value;
    public Kazu(int n){
	value = n;
    }
}
class Wa extends Node {
    private char op;
    private Node left;
    private Node right;
    public Wa(){}
    public void setOp(char op){
	this.op = op;
    }
    public void setLeft(Node n){
	left = n;
    }
    public void setRight(Node n){
	right = n;
    }
}

class Node:
    pass
class Kazu(Node):
    def __init__(self, n):
        self.value = n

class Wa(Node):
    def setOp(self, op):
	self.op = op

    def setLeft(self, n):
	self.left = n

    def setRight(self, n):
	self.right = n

abstract class Node {
    abstract public void setOp(char op);
    abstract public void setLeft(Node n);
    abstract public void setRight(Node n);
}

class Rei {
    public static void main(String[] arg){
	final Node tmp = new Wa();
	tmp.setOp('+');
	tmp.setLeft(new Kazu(1));
	tmp.setRight(new Kazu(2));
	final Node root = new Wa();
	root.setOp('+');
	root.setLeft(tmp);
	root.setRight(new Kazu(3));
    }
}

tmp = Wa()
tmp.setOp('+')
tmp.setLeft(Kazu(1))
tmp.setRight(Kazu(2))
root = Wa()
root.setOp('+')
root.setLeft(tmp)
root.setRight(Kazu(3))

abstract class Node {
    abstract public void showExpression();
}
class Kazu extends Node {
    @Override
    public void showExpression(){
	System.out.print(value);
    }
}
class Wa extends Node {
    @Override
    public void showExpression(){
	System.out.print('(');
	left.showExpression();
	System.out.print(op);
	right.showExpression();
	System.out.print(')');
    }
}

class Node:
    pass
class Kazu(Node):
    def showExpression(self):
        print(self.value)
class Wa(Node):
    def showExpression(self):
        print('(')
	self.left.showExpression()
	print(self.op)
	self.right.showExpression()
	print(')')

abstract class Node {
    abstract public void rpn();
}
class Kazu extends Node {
    @Override
    public void rpn(){
	System.out.print(value+" ");
    }
}
class Wa extends Node {
    @Override
    public void rpn(){
	left.rpn();
	right.rpn();
	System.out.print(op+" ");
    }
}

class Node:
    pass

class Kazu(Node):
    def rpn(self):
        print(self.value+" ")

class Wa(Node):
    def rpn(self):
        self.left.rpn()
        self.right.rpn()
        print(self.op+" ")

/* G1 による構文解析木(ただし動作しない) 
   エラー処理はかなり適当
*/
class Parser {
    public Node wa(){
        if(入力が適合){
           Node result = new Wa();
           result.setLeft(wa());
           result.setOp(lastChar);
           nextChar();
           result.setRight(kazu());
           return result;
        }
        return null;
    }
    public Node kazu(){
        if(入力が適合){
           return new Kazu(lastChar);
        }
        return null;
    }
}

# G1 による構文解析木(ただし動作しない) 
# エラー処理はかなり適当
class Parser:
    def wa(self):
        if 入力が適合:
            result = Wa()
            result.setLeft(wa())
            result.setOp(Parser.lastChar)
            Parser.nextChar()
            result.setRight(kazu())
            return result
        else:
            return null
    def kazu(self):
        if 入力が適合:
           return Kazu(Parser.lastChar)
                }
        return null

class Wa extends Node {
    public static Node connectToLeft(Node n){
        final Wa result = new Wa();
        result.setLeft(n);
        return result;
    }
}

class Wa(Node):
    @classmethod
    def connectToLeft(cls,n):
        result = Wa()
        result.setLeft(n)
        return result

import java.io.*;
class Parser {
    final private Reader reader;
    public Parser(Reader r) throws IOException{
	reader = r;
	c = reader.read();
    }
    private int c;
    private Node root;
    public Node s() throws IOException{
	if(Character.isDigit(c)){
	    if(wa1()){
		if(c=='='){
		    c = reader.read();
		    return root;
		}
	    }
	}
	return null;
    }
    private boolean wa1() throws IOException{
	System.err.println("called wa1.");
	if(Character.isDigit(c)){
	    root = new Kazu(c-'0');
	    c = reader.read();
	    if(wa2()){
		return true;
	    }
	}
	return false;
    }
    private boolean wa2() throws IOException{
	System.err.println("called wa2.");
	if(c=='='){
	    return true;
	}
	if(c=='+'){
            char op = (char) c;
	    c = reader.read();
	    if(Character.isDigit(c)){
		root = Wa.connectToLeft(root);
	        root.setOp(op);
		root.setRight(new Kazu(c-'0'));
		c = reader.read();
		if(wa2()){
		    return true;
		}
	    }
	}
	return false;
    }
	
}
class Rei {
    public static void main(String[] arg) throws IOException{
	final Reader r = new InputStreamReader(System.in);
	final Parser parser = new Parser(r);
	Node tree = parser.s();
	if(tree !=null){
	    tree.showExpression();
	    tree.rpn();
	}
    }
}

class Reader:
    def __init__(self, string):
        self.l = list(string)
        self.p = 0

    def read(self):
        if self.p >= len(self.l):
            raise StopIteration()
        result = self.l[self.p]
        self.p += 1
        return result
    
class Parser:
    def __init__(self, r):
        self.reader = r
        self.c = self.reader.read()

    def s(self):
        if self.c.isdecimal():
            if self.wa1():
                if self.c=='=':
#                    self.c = self.reader.read()
                    return self.root
        return None
    def wa1(self):
        print("called wa1.")
        if self.c.isdecimal():
            self.root = Kazu(int(self.c))
            self.c = self.reader.read()
            if self.wa2():
                return True
        return False

    def wa2(self):
        print("called wa2.")
        if self.c=='=':
            return True
        if self.c=='+':
            op = self.c;
            self.c = self.reader.read()
            if self.c.isdecimal():
                self.root = Wa.connectToLeft(self.root)
                self.root.setOp(op)
                self.root.setRight(Kazu(int(self.c)))
                self.c = self.reader.read()
                if self.wa2():
                    return True
        return False

r = Reader(input())
parser = Parser(r)
tree = parser.s()
if tree != None:
    tree.showExpression()
    print()
    tree.rpn()
    print()

abstract class Node {
    abstract public void setOp(char op);
    abstract public void setLeft(Node n);
    abstract public void setRight(Node n);
    abstract public void showExpression();
    abstract public void rpn();
}
class Kazu extends Node {
    private int value;
    public Kazu(int n){
	value = n;
    }
    @Override
    public void showExpression(){
	System.out.print(value);
    }
    @Override
    public void rpn(){
	System.out.print(value+" ");
    }
}
class Wa extends Node {
    private char op;
    private Node left;
    private Node right;
    public Wa(){}
    public void setOp(char op){
	this.op = op;
    }
    public void setLeft(Node n){
	left = n;
    }
    public void setRight(Node n){
	right = n;
    }
    public static Node connectToLeft(Node n){
        final Wa result = new Wa();
        result.setLeft(n);
        return result;
    }
    @Override
    public void showExpression(){
	System.out.print('(');
	left.showExpression();
	System.out.print(op);
	right.showExpression();
	System.out.print(')');
    }
    @Override
    public void rpn(){
	left.rpn();
	right.rpn();
	System.out.print(op+" ");
    }
}
import java.io.*;
class Parser {
    final private Reader reader;
    public Parser(Reader r) throws IOException{
	reader = r;
	c = reader.read();
    }
    private int c;
    private Node root;
    public Node s() throws IOException{
	if(Character.isDigit(c)){
	    if(wa1()){
		if(c=='='){
		    c = reader.read();
		    return root;
		}
	    }
	}
	return null;
    }
    private boolean wa1() throws IOException{
	System.err.println("called wa1.");
	if(Character.isDigit(c)){
	    root = new Kazu(c-'0');
	    c = reader.read();
	    if(wa2()){
		return true;
	    }
	}
	return false;
    }
    private boolean wa2() throws IOException{
	System.err.println("called wa2.");
	if(c=='='){
	    return true;
	}
	if(c=='+'){
            char op = (char) c;
	    c = reader.read();
	    if(Character.isDigit(c)){
		root = Wa.connectToLeft(root);
	        root.setOp(op);
		root.setRight(new Kazu(c-'0'));
		c = reader.read();
		if(wa2()){
		    return true;
		}
	    }
	}
	return false;
    }
	
}
class Rei {
    public static void main(String[] arg) throws IOException{
	final Reader r = new InputStreamReader(System.in);
	final Parser parser = new Parser(r);
	Node tree = parser.s();
	if(tree !=null){
	    tree.showExpression();
	    tree.rpn();
	}
    }
}

class Node:
    pass

class Kazu(Node):
    def __init__(self, n):
        self.value = n
    def showExpression(self):
        print(self.value,end="")
    def rpn(self):
        print(self.value," ",end="")

class Wa(Node):
    def setOp(self, op):
        self.op = op

    def setLeft(self, n):
        self.left = n

    def setRight(self, n):
        self.right = n
    def rpn(self):
        self.left.rpn()
        self.right.rpn()
        print(self.op," ",end="")
    def showExpression(self):
        print('(',end="")
        self.left.showExpression()
        print(self.op,end="")
        self.right.showExpression()
        print(')',end="")
    @classmethod
    def connectToLeft(cls,n):
        result = Wa()
        result.setLeft(n)
        return result
class Reader:
    def __init__(self, string):
        self.l = list(string)
        self.p = 0

    def read(self):
        if self.p >= len(self.l):
            raise StopIteration()
        result = self.l[self.p]
        self.p += 1
        return result
    
class Parser:
    def __init__(self, r):
        self.reader = r
        self.c = self.reader.read()

    def s(self):
        if self.c.isdecimal():
            if self.wa1():
                if self.c=='=':
#                    self.c = self.reader.read()
                    return self.root
        return None
    def wa1(self):
        print("called wa1.")
        if self.c.isdecimal():
            self.root = Kazu(int(self.c))
            self.c = self.reader.read()
            if self.wa2():
                return True
        return False

    def wa2(self):
        print("called wa2.")
        if self.c=='=':
            return True
        if self.c=='+':
            op = self.c;
            self.c = self.reader.read()
            if self.c.isdecimal():
                self.root = Wa.connectToLeft(self.root)
                self.root.setOp(op)
                self.root.setRight(Kazu(int(self.c)))
                self.c = self.reader.read()
                if self.wa2():
                    return True
        return False

r = Reader(input())
parser = Parser(r)
tree = parser.s()
if tree != None:
    tree.showExpression()
    print()
    tree.rpn()
    print()

abstract class Node {
    abstract <T> T accept(Visitor<T> visitor);
}
class NumberNode extends Node {
    private final double value;
    public NumberNode(double value) {
        this.value = value;
    }
    public double getValue() {
        return value;
    }
    @Override
    <T> T accept(Visitor<T> visitor) {
        return visitor.visit(this);
    }
}
class BinaryOperatorNode extends Node {
    private final char operator;
    private final Node left;
    private final Node right;
    public BinaryOperatorNode(char operator, Node left, Node right) {
        this.operator = operator;
        this.left = left;
        this.right = right;
    }
    public char getOperator() {
        return operator;
    }
    public Node getLeft() {
        return left;
    }
    public Node getRight() {
        return right;
    }
    @Override
    <T> T accept(Visitor<T> visitor) {
        return visitor.visit(this);
    }
}
interface Visitor<T> {
    T visit(NumberNode node);
    T visit(BinaryOperatorNode node);
}
class EvaluateVisitor implements Visitor<Double> {
    @Override
    public Double visit(NumberNode node) {
        return node.getValue();
    }

    @Override
    public Double visit(BinaryOperatorNode node) {
        double leftValue = node.getLeft().accept(this);
        double rightValue = node.getRight().accept(this);

        switch (node.getOperator()) {
            case '+':
                return leftValue + rightValue;
            case '-':
                return leftValue - rightValue;
            case '*':
                return leftValue * rightValue;
            case '/':
                return leftValue / rightValue;
            default:
                throw new UnsupportedOperationException("Unknown operator: " + node.getOperator());
        }
    }
}
class RPNVisitor implements Visitor<String> {
    @Override
    public String visit(NumberNode node) {
        return Double.toString(node.getValue());
    }

    @Override
    public String visit(BinaryOperatorNode node) {
        String left = node.getLeft().accept(this);
        String right = node.getRight().accept(this);
        return left + " " + right + " " + node.getOperator();
    }
}
class InfixVisitor implements Visitor<String> {
    @Override
    public String visit(NumberNode node) {
        return Double.toString(node.getValue());
    }

    @Override
    public String visit(BinaryOperatorNode node) {
        String left = node.getLeft().accept(this);
        String right = node.getRight().accept(this);
        return "(" + left + " " + node.getOperator() + " " + right + ")";
    }
}
class Main {
    public static void main(String[] args) {
        Node expression = new BinaryOperatorNode('+',
                new NumberNode(3),
                new BinaryOperatorNode('*',
                        new NumberNode(4),
                        new NumberNode(5)));

        EvaluateVisitor evaluateVisitor = new EvaluateVisitor();
        double result = expression.accept(evaluateVisitor);
        System.out.println("Result: " + result);

        RPNVisitor rpnVisitor = new RPNVisitor();
        String rpnExpression = expression.accept(rpnVisitor);
        System.out.println("RPN Expression: " + rpnExpression);

        InfixVisitor infixVisitor = new InfixVisitor();
        String infixExpression = expression.accept(infixVisitor);
        System.out.println("Infix Expression: " + infixExpression);
    }
}

class Node:
    def accept(self, visitor):
        pass
class NumberNode(Node):
    def __init__(self, value):
        self.value = value
    def accept(self, visitor):
        return visitor.visit_number(self)
class BinaryOperatorNode(Node):
    def __init__(self, operator, left, right):
        self.operator = operator
        self.left = left
        self.right = right
    def accept(self, visitor):
        return visitor.visit_binary_operator(self)
class Visitor:
    def visit_number(self, node):
        pass
    def visit_binary_operator(self, node):
        pass
class EvaluateVisitor(Visitor):
    def visit_number(self, node):
        return node.value
    def visit_binary_operator(self, node):
        left = node.left.accept(self)
        right = node.right.accept(self)
        if node.operator == '+':
            return left + right
        elif node.operator == '-':
            return left - right
        elif node.operator == '*':
            return left * right
        elif node.operator == '/':
            return left / right
class RPNVisitor(Visitor):
    def visit_number(self, node):
        return str(node.value)
    def visit_binary_operator(self, node):
        left = node.left.accept(self)
        right = node.right.accept(self)
        return f"{left} {right} {node.operator}"
class InfixVisitor(Visitor):
    def visit_number(self, node):
        return str(node.value)
    def visit_binary_operator(self, node):
        left = node.left.accept(self)
        right = node.right.accept(self)
        return f"({left} {node.operator} {right})"

expression = BinaryOperatorNode('+',
    NumberNode(3),
    BinaryOperatorNode('*',
        NumberNode(4),
        NumberNode(5)))

evaluate_visitor = EvaluateVisitor()
result = expression.accept(evaluate_visitor)
print("Result:", result)

rpn_visitor = RPNVisitor()
rpn_expression = expression.accept(rpn_visitor)
print("RPN Expression:", rpn_expression)

infix_visitor = InfixVisitor()
infix_expression = expression.accept(infix_visitor)
print("Infix Expression:", infix_expression)