진실 테이블 생성기를 어떻게 구축 할 수 있습니까?

StackOverflow https://stackoverflow.com/questions/1084873

문제

개인 프로젝트로 진실 테이블 생성기를 쓰려고합니다.

몇 가지 웹 기반 온라인이 있습니다 여기 그리고 여기.

alt text
(Example screenshot of an existing Truth Table Generator)

다음 질문이 있습니다.

  • 다음과 같은 표현을 구문 분석하는 방법은 다음과 같습니다. ((p => q) & (q => r)) => (p => r)
  • Antlr 또는 YACC와 같은 파서 생성기를 사용해야합니까, 아니면 직선 정규 표현식을 사용해야합니까?
  • 표현이 구문 분석되면 어떻게 진실 테이블을 생성해야합니까? 표현식의 각 섹션은 가장 작은 구성 요소로 나누고 테이블의 왼쪽에서 오른쪽으로 다시 제작해야합니다. 그런 것을 어떻게 평가합니까?

누구든지 이러한 임의의 표현의 구문 분석에 관한 팁을 제공하고 결국 구문 분석 된 표현을 평가할 수 있습니까?

도움이 되었습니까?

해결책

이것은 훌륭한 개인 프로젝트처럼 들립니다. 컴파일러의 기본 부분이 어떻게 작동하는지에 대해 많은 것을 배울 것입니다. 나는 파서 생성기를 사용하려고 노력할 것입니다. 이것이 당신 자신의 교화를위한 것이라면, 당신은 처음부터 모든 것을함으로써 더 많은 것을 배울 것입니다.

그러한 시스템이 작동하는 방식은 우리가 자연 언어를 이해하는 방법을 공식화하는 것입니다. 내가 당신에게 문장을 주면 : "개, 로버, 음식을 먹었습니다." "The", "Space", "Dog", "Comma", "Space", "Rover", ... "Tokenizing"또는 "Lexing"입니다.

다음으로하는 일은 문장이 문법인지 확인하기 위해 토큰 스트림을 분석하는 것입니다. 영어의 문법은 매우 복잡하지만이 문장은 매우 간단합니다. 주제-적용 비방-객체. 이것은 "파싱"입니다.

문장이 문법이라는 것을 알면 문장을 분석하여 실제로 의미를 얻을 수 있습니다. 예를 들어,이 문장의 세 부분 (주제, Appositive 및 Object)의 세 부분이 모두 같은 실체, 즉 개를 의미합니다. 당신은 개가 먹는 일이며 음식은 먹는 것임을 알 수 있습니다. 이것은 시맨틱 분석 단계입니다.

그런 다음 컴파일러는 인간이하지 않는 네 번째 단계를 가지고 있으며, 이는 언어에 설명 된 행동을 나타내는 코드를 생성합니다.

그래서, 그 모든 것을하십시오. 언어의 토큰이 무엇인지 정의하여 시작하고, 기본 클래스 토큰과 각각의 파생 클래스를 정의하십시오. (식별, ortoken, and token, empliestoken, rightparentoken ...). 그런 다음 문자열을 취하고 ienumerable을 반환하는 메소드를 작성하십시오. 그게 당신의 렉서입니다.

둘째, 언어의 문법이 무엇인지 알아 내고, 당신의 언어의 문법적 실체를 나타내는 추상 구문 트리에 ienumerible을 분해하는 재귀 적 하강 구문서를 작성하십시오.

그런 다음 그 나무를 보는 분석기를 작성하고 "몇 개의 별개의 자유 변수가 있습니까?"와 같이 그림을 피하십시오.

그런 다음 진실 테이블을 평가하는 데 필요한 코드를 제시하는 코드 생성기를 작성하십시오. Spitting Il은 과잉처럼 보이지만, 정말로 버프가되고 싶다면 할 수 있습니다. Expression Tree 라이브러리가 당신을 위해 그렇게하도록하는 것이 더 쉬울 수 있습니다. 구문 분석 트리를 표현 트리로 변환 한 다음 표현식 트리를 대의원으로 바꾸고 대의원을 평가할 수 있습니다.

행운을 빕니다!

다른 팁

파서 생성기가 과잉이라고 생각합니다. 표현식을 PostFix로 변환하는 아이디어를 사용할 수 있습니다. 포스트 픽스 표현식 평가 이 문제를 해결하기 위해 (또는 디스 픽스 표현식에서 발현 트리를 직접 구축하고 진리 테이블을 생성).

Mehrdad가 언급했듯이 Lexer/Parser의 구문을 배우는 데 걸리는 것과 동시에 구문 분석을 손으로 굴릴 수 있어야합니다. 당신이 원하는 최종 결과는 당신이 주신 표현의 추상 구문 트리 (AST)입니다.

그런 다음 표현식에 정의 된 기호의 입력 조합을 생성하는 입력 생성기를 빌드해야합니다.

그런 다음 입력 세트를 반복하여 첫 번째 단계에서 구문 분석 한 규칙 (AST)이 주어지면 각 입력 콤보의 결과를 생성합니다.

내가 어떻게 할 것인가 :

Lambda 함수를 사용하여 트리를 구문 분석 할 때 AST/규칙을 표현하고 구문 분석 할 때 기호 테이블을 만들면 입력 세트를 작성하여 기호 테이블을 Lambda Expression Tree에 구문 분석하여 결과를 계산할 수 있습니다.

당신의 목표가 부울 표현을 처리하는 것이라면, 파서 생성기 및 함께가는 모든 기계는 시간 낭비입니다.

그러나 부울 표현을 위해 재귀 살해 파서를 직접 구축하는 것은 쉽고, 표현을 "평가"한 결과를 계산하고 반환합니다. 이러한 파서는 첫 번째 패스에서 고유 한 변수의 수를 결정하기 위해 첫 번째 패스에서 사용될 수 있으며, 여기서 "평가"는 "각각의 새로운 변수 이름에 대한 couunt 1"을 의미합니다. n 변수에 대한 모든 가능한 진실 값을 생성하기 위해 생성기를 작성하는 것은 사소한 일입니다. 각 값 세트에 대해 구문자를 다시 호출하여이를 사용하여 표현식을 평가하는데, 여기서 평가는 "연산자에 따라 하위 표현의 값을 결합"하는 것을 의미합니다.

문법이 필요합니다.

formula = disjunction ;
disjunction = conjunction 
              | disjunction "or" conjunction ;
conjunction = term 
              | conjunction "and" term ;
term = variable 
       | "not" term 
       |  "(" formula ")" ;

당신은 더 복잡 할 수 있지만 부울 표현의 경우 훨씬 더 복잡 할 수는 없습니다.

각 문법 규칙에 대해 글로벌 "스캔"인덱스를 사용하는 문자열에 구문 분석하는 문자열 1 개를 작성하십시오.

  int disjunction()
 // returns "-1"==> "not a disjunction"
 // in mode 1:
 // returns "0" if disjunction is false
 // return  "1" if disjunction is true
 { skipblanks(); // advance scan past blanks (duh)
   temp1=conjunction();
   if (temp1==-1) return -1; // syntax error
   while (true)
     { skipblanks();
       if (matchinput("or")==false) return temp1;
       temp2= conjunction();
       if (temp2==-1) return temp1;
       temp1=temp1 or temp2;
     }
  end

  int term()
  { skipblanks();
    if (inputmatchesvariablename())
       { variablename = getvariablenamefrominput();
         if unique(variablename) then += numberofvariables;
         return lookupvariablename(variablename); // get truthtable value for name
       }
     ...
  }

각 구문 분석 루틴은이 복잡한 일입니다. 진지하게.

pyttgen 프로그램의 소스 코드를 얻을 수 있습니다 http://code.google.com/p/pyttgen/source/browse/#hg/src 그것은 논리적 표현에 대한 진실 테이블을 생성합니다. Ply 라이브러리를 기반으로 한 코드이므로 매우 간단합니다 :)

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top