통일 알고리즘이 프롤로그에서 어떻게 작동하는지 이해하기 위해 지난 5 일 동안 작업했습니다. 는 지금, 나는통일 알고리즘 구현
이 명확하게하기 위해 ..
내가 아마 가장 좋은 방법은 문자열을 조작 및 스택과 같은 몇 가지 자료 구조를 사용하여 부품을 분해하는 생각 .. 자바와 같은 알고리즘을 구현하려는 :사용자 입력이 : a (X, c (d, X)) = a (2, c (d, Y))라고 가정합니다.
이미 하나의 문자열로 가져 와서 두 개의 문자열 (Expression1과 2)로 나눕니다. 지금, 다음 문자 (들)이 변수 또는 상수 등인지 알 수 있습니까? 중첩으로 할 수 있지만 좋은 해결책이 아닌 것 같습니다. 상속을 사용하려고했지만 문제가 있습니다. 아직도 (글자의 타입을 어떻게 알 수 있습니까?)
이 문제는 통일보다 구문 분석과 관련이있는 것으로 들립니다. ANTLR과 같은 것을 사용하면 원래 문자열을 일종의 트리 구조로 변환하는 데 도움이 될 수 있습니다.
("중첩하여 수행"이 무슨 뜻인지는 분명치 않지만, 표현을 읽으려는 것과 같은 것을하고, 각각 "(", 실제로는 하나입니다. ANTLR이 생성하는 코드가 마음에 들었습니다.)
구문 분석하는 것보다 통합하는 방법에 더 관심이 있다면 완벽하게 좋은 것입니다 이 작업을 수행하는 방법은 코드에서 직접 내부 표현을 구성하고 지금은 구문 분석 측면을 없애는 것입니다.이 방법은 개발 중에 Prolog 스타일 구문이 다소 장황한 Java 구문 집합이므로 조금 성가 시지만 한 번에 한 가지 문제에만 집중할 수 있으며, 이는 일반적으로 도움이됩니다.
(이런 식으로 구조를 만들면 적절한 파서를 나중에 삽입하면 그때까지 수작업으로 구성한 것과 같은 트리가 생성됩니다. 이것은 합리적으로 깔끔한 방식으로 두 가지 문제를 개별적으로 공격하게합니다.)
먼저 입력을 구문 분석하고 표현 트리를 작성해야합니다. 그런 다음 Milner의 통합 알고리즘 (또는 다른 통일 알고리즘)을 적용하여 상수와 표현식에 대한 변수 매핑을 찾습니다.
Milner의 알고리즘에 대한 설명은 Aho, Sethi 및 Ullman의 "컴파일러 : 원리, 기법 및 도구"에서 찾을 수 있습니다. Milner 알고리즘은 순환 적 그래프의 통일에 대처할 수 있으며, Dragon Book은 이것을 유형 유추를 수행하는 방법으로 제시합니다. 그것의 소리에 의해 당신은 파싱에 관해 조금 배우는 것에서 이익을 얻을 수 있습니다 ... 또한 드래곤 북 (Dragon Book)에 의해 보호됩니다.
EDIT : 다른 답변은 파서 생성기를 사용하여 제안했습니다. 예 : ANTLR. 좋은 조언이지만, 문법은 너무 단순해서 StringTokenizer와 손으로 작성한 재귀 적 파서를 사용하여 얻을 수 있습니다. 사실, 시간 (그리고 성향)이 있다면 파서를 두 가지 방법 모두를 학습 연습으로 구현할 가치가 있습니다.
언어의 의미를 익히기 전에 텍스트를 조작하기 쉬운 형식으로 변환해야합니다. 이 과정은 parsing이고 의미 론적 표현은 abstract syntax tree (AST)이라고합니다.
프롤로그에 대한 간단한 재귀 하강 파서는 손으로 쓴, 그러나 당신이 기간의 클래스가있을 수 있습니다, 프롤로그에 대한 AST에서 파서 툴킷과 같은 Rats! 또는 Antlr
를 사용하는 일반적인, 그리고 CompoundTerm 수 있습니다, 변수 및 원자는 모두 조건입니다. 다형성은 복합 용어에 대한 인수를 임의의 용어로 허용합니다.
그러면 통일 알고리즘은 복합 용어의 이름을 통합하고 해당 복합 용어의 각 인수 값을 재귀 적으로 통합합니다.