추상 구문 트리에서 제어 흐름 그래프 가져오기

https://stackoverflow.com/questions/92537

01-07-2019
|

문제

Java용 ANTLR Parser Generator에서 파생된 AST가 있습니다.내가 원하는 것은 소스 코드의 제어 흐름 그래프를 어떻게든 구성하는 것입니다. 여기서 각 명령문이나 표현식은 고유한 노드입니다.나는 이 식별에 어느 정도 재귀성이 있어야 한다는 것을 이해합니다. 귀하가 최선의 선택으로 무엇을 제안할지, ANTLR에 이 작업에 사용할 수 있는 도구 세트가 있는지 궁금합니다.건배, 크리스

편집 - 나의 주요 관심사는 AST에서 제어 흐름 그래프(CFG)를 얻는 것입니다.이렇게 하면 소스의 트리 표현을 얻을 수 있습니다.명확히 말하면 소스 코드와 구현 언어는 모두 Java입니다.

해결책

일반적으로 CFG는 하위 수준 표현(예:JVM 바이트코드).누군가 그랬어요 논문 몇 년 전에는 그런 일에 대해서요.해당 표현을 얻는 방법에 대한 유용한 방법이 거기에 설명되어 있을 수 있습니다.

소스 언어와 대상 언어가 동일하므로 코드 생성 단계가 없습니다. 이미 완료되었습니다!그러나 이제 AST를 걸어야 합니다.AST의 각 노드에서 스스로에게 질문해야 합니다.이것은 "점프" 지시인가, 아닌가?메서드 호출과 if 문은 점프 명령의 예입니다.루프 구성(예: for 그리고 while).덧셈, 곱셈 등의 명령은 점프하지 않습니다.

먼저 각 Java 문과 CFG의 노드를 시작 및 종료 노드와 연결합니다.첫 번째 근사치로 트리를 탐색하고 다음을 수행합니다.

현재 문이 메서드 호출인 경우 해당 메서드 호출의 해당 본문에 대한 항목 노드가 어디에 있는지 파악하고 현재 문에서 해당 항목 노드를 가리키는 가장자리를 만듭니다.명령문이 메소드 반환인 경우 이를 호출할 수 있는 위치를 열거하고 해당 위치에 가장자리를 추가합니다.
점프하지 않는 각 문에 대해 해당 문과 다음 문 사이에 가장자리를 만듭니다.

이것은 당신에게 줄 것입니다 어떤 종류의 CFG의호출된 메소드가 AST의 다른 곳이 아닌 라이브러리에서 선언될 수 있기 때문에 2단계에서 절차가 약간 복잡해집니다. 그렇다면 가장자리를 만들지 않거나 해당 항목을 나타내는 특수 노드에 가장자리를 만드십시오. 도서관 방법.

이게 말이 돼?

다른 팁

모든 언어 문제를 실제로 고려하는 전체 제어 흐름 그래프를 생성하는 것은 보이는 것보다 어렵습니다."기본 블록"인 것으로 보이는 것을 식별해야 할뿐만 아니라 기능 호출을 식별해야합니다 (쉽지 않지만 식별합니다. 표적 클래스 이니셜 라이저와 같은 비하인드 작업이 발생할 수있는 경우에는 더 어려울 수 있습니다.예외가 발생할 수있는 지점과 예외가 발생하면 제어가 진행되는지에 대해 걱정합니다.

대부분의 언어를주의 깊게 검사하면 표현식 계산 평가 순서에 대해서는 분명하며, 이는 표현식에 두 가지 부작용이있는 경우 중요합니다.제어 흐름은 순서 (또는 정의되지 않은 경우 비 주문)를 반영해야합니다.

어쩌면 당신은 기본 블록과 조건부가있는 제어 흐름의 추상화를 원할 것입니다.분명히 조금 더 쉽습니다.

두 경우 모두 (간단한 CFG 또는 전체 CFG), 가능한 제어 흐름 목표에 대한 참조를 갖는 각 지점에서 AST를 걸어야합니다 (예 : 대부분의 경우 IF 문과 같은 두 가지 유량 목표가 있습니다.THEN 및 ELSE 절).각 노드에서 해당 노드를 적절한 제어 흐름 대상에 연결하여 흐름 대상을 대체 할 수 있습니다 (예 : IF가 발생할 때).

Java (또는 C)의 전체 언어 의미론을 위해 이것을하는 것은 많은 일입니다.이 기성품을 계산하는 도구를 간단히 사용하고 싶을 수도 있습니다.보다 http://www.semanticdesigns.com/Products/DMS/FlowAnalytic.html이것이 실제로 어떤 모습인지, 우리 도구에서 나오는 것입니다.

일부 의견에 따르면 OP가 정말로 원하는 것 같습니다. 코드 생성 -- AST를 기본 블록 및 점프 포인트를 기반으로 하는 하위 수준 명령어 시퀀스로 변환합니다.

코드 생성은 언어별로 매우 구체적이며 이 주제에 대해 많은 작업이 이루어졌습니다.코드 생성을 수행하기 전에 알아야 할 사항 대상 언어 -- 어셈블러든 다른 고급 언어든 상관없습니다.이를 식별한 후에는 AST를 살펴보고 AST에서 코드를 구현하는 일련의 명령을 생성하기만 하면 됩니다.(간단하지만 어려울 수 있습니다. 여기서 고려 사항은 언어별로 상당히 다르기 때문에 일반화하기가 어렵습니다.)

코드 생성을 위해 선택한 표현에는 암시적 또는 명시적으로 제어 흐름 그래프가 포함됩니다.대상 언어가 상당히 낮은 수준(어셈블러에 가까움)인 경우 제어 흐름 그래프는 상대적으로 쉽게 추출할 수 있습니다.

(자세한 설명을 원하시면 댓글을 남겨주세요.)

혹시 시도해 보셨나요? ANTLR 스튜디오?홀 AST 그래프를 생성하지는 않지만 검토를 위해 이미 꽤 유용합니다.

과거에 이 작업을 수행했을 때 다음을 사용했습니다. 그래프 시각화, 특히 도트 도구를 사용하여 그래프를 생성합니다.컴파일 타임에 제어 흐름 그래프를 실제로 순회하여 도트 입력 파일을 만들었습니다.

그래프 레이아웃은 어려운 문제, graphviz는 훌륭한 작업을 수행합니다.ps, pdf 및 다양한 이미지 형식으로 출력할 수 있으며 레이아웃은 일반적으로 보기에 매우 직관적입니다.나는 그것을 강력히 추천합니다.

나는 ANTLR에서 AST 유무에 관계없이 CFG를 생성하는 방법을 모르기 때문에 귀하가 찾고 있는 방식으로 귀하의 질문에 대답할 수 없을 것이라고 생각합니다.그러나 간단히 말해서 ANTLR이 생성하는 것을 사용하여 별도의 Java 프로그램을 생성하여 CFG를 생성하게 됩니다.ANTLR에서 생성된 구문 트리를 입력으로 활용하여 직접 만든 별도의 Java 프로그램에서 CFG를 생성할 수 있습니다.이 시점에서는 본질적으로 컴파일러를 구축하고 있습니다."컴파일러"와 JVM의 차이점은 출력이 프로그램이 다양한 실행 경로를 분기하는 방법에 대한 시각적 표현(CFG)이고 JVM/Java 컴파일러는 실제 머신(CPU)에서 실행하기 위한 코드를 생성한다는 것입니다.

비유는 누군가가 책을 쓰기 위해 앉아 있는 경우(예를 들어 영어로) 문장에 사용된 개별 단어는 컴퓨터 언어의 토큰이고 문장은 문맥 자유 문법이 유효한 컴퓨터 코드를 표현하는 것과 유사한 방식으로 형성되며 문단은 & 전체 소설은 의미 분석/컴파일러/CFG가 실제로 유용한 작업을 수행하고 논리 버그가 거의 없는 논리적으로 유효한 프로그램을 생성/표현할 수 있는 것과 유사한 방식으로 이야기를 전달합니다.즉, 유효한 구문(올바른 문장 구조) 문제를 통과하면 누구나 페이지에 여러 문장을 작성할 수 있지만 특정 문장 조합만이 실제로 무언가(이야기 전달)를 수행하는 텍스트를 생성합니다.

당신이 묻고 있는 것은 마지막 부분, 즉 구문 트리를 취하고 AST가 실제로 수행하는 작업을 논리적으로 변환하거나 해석하는 방법입니다.물론 이 작업을 수행하려는 각 언어에 대해 "컴파일러"를 구축해야 합니다.올바른 문법을 가지고 있다고 해서 알 수는 없습니다. 무엇 프로그램은 그렇습니다. 단지 프로그램이 문법 관점에서 올바르다는 것입니다.

린터와 구문 하이라이터, IDE는 모두 이 마지막 퍼즐 조각을 인간이 더 쉽고 효율적으로 작업할 수 있도록 하려는 아이디어를 바탕으로 구축되었습니다.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow