Im viết trình biên dịch cho dự án đại học và tôi muốn chuyển đổi Abstract Syntax Tree thành Biểu đồ luồng điều khiển (CFG).Xây dựng chính thức Biểu đồ luồng điều khiển
Tôi nghĩ rằng các nút (V) trong CFG phải là các nút từ AST. Tôi biết thuật toán làm thế nào để xây dựng tập cạnh (G=(V,E)) nhưng Im có một thời gian khó viết quá trình này một chút chính thức hơn
tôi đã tạo ra này hoa văn phong cách phù hợp với scala (Pseudo):
def edges(n:Node)(nestedin_next: Node) : List[(Node,Node)] =
n match {
case (c_1 :: c_2::tl) => (c1,c2) :: edges(c2::tl)(nestedin_next)++
edges(c_1)(c_2)//recurse
case c_1 :: Nil => (c_1,nestedin_next)::Nil
case [email protected] IF(_,c1,c2) => (i,c1)::(i,c2)::edges(c1)(nestedin_next)++
edges(c2)(nestedin_next)
case _ => Nil
}
nào phải phù hợp với một cấu trúc AST như:
(IF(1,
ASSIGN(x,1), // ia1
ASSIGN(x,2) // ia2
) :: // i1
ASSIGN(y,2) :: // a1
ASSIGN(z,ADD(x,y)) :: //a2
IF(z,
RET(z), //i2r1
assign(z,0):: // i2a1
ret(z) // i2r2
) :://i2
Nil
)
và cung cấp một edgeset như:
{ i1 -> ia1,
i1 -> ia2,
ia1 -> a1,
ia2 -> a1,
a1 -> a2,
a2 -> i2,
i2 -> i2r1
i2-> i2a1
i2a1 -> i2r2
i2r2 -> _|_
i2r1 -> _|_
}
Bất cứ ai có bất kỳ gợi ý về cách để làm điều này một chút chính thức hơn scala "giả"?
Im suy nghĩ một cái gì đó quy nạp như:
e[[ IF(_,b1,b2) ]] = (if -> b1) + (if -> b2) \cup e[[ b1 ]] \cup e[[ b2 ]]
e[[ b1, b2 ]] = e[[b1]] \cup e[[b2]]
(ở trên sẽ chỉ cung cấp cho một cái cây và không phải là một đồ thị mặc dù Không cạnh từ mép sau đó ngành để tuyên bố tiếp theo ví dụ.)
EDIT :
Tôi đã đọc lên trên kiama and dataflows cho scala và tôi thích phương pháp "succ" và "theo dõi" mà họ sử dụng. Tuy nhiên, tôi đang gặp khó khăn trong việc đun sôi nó thành một mô tả chính thức hơn, chủ yếu là bởi vì các số childAttr, s.next tiện lợi, ẩn một số chi tiết biến xấu xí khi tôi cố gắng chỉ định nó một cách chính thức.
EDIT2:
Tôi đã trải qua Sách Dragon và "Modern Compiler Thực hiện trong ML" cũng như một số các vật chất khác từ Learning to write a compiler và một số/đề cập đến hầu hết các luồng dữ liệu và kiểm soát dòng chảy, nhưng không bao giờ chạm nhiều khi LÀM THẾ NÀO để tạo CFG theo bất kỳ cách thức chính thức nào.
EDIT3:
Via Kiama tác giả, Associate Professor Dr. Tony Sloane tôi nhận được một số additional book references to look up.
Theo tôi có thể thấy "cách thực hiện" theo những sách đó dựa trên "mỗi câu lệnh" của chương trình nhiều hơn AST và dựa trên các khối cơ bản. Tuy nhiên, đầu vào tuyệt vời!
Tôi hy vọng bạn không nhớ rằng tôi đã thêm "scala" vào thẻ. –
@Randall Không phải tất cả :) Tôi gần như đã làm như vậy tự của tôi – svrist