diff --git a/cc/cc.go b/cc/cc.go
index 4ec98be..fdf2879 100644
--- a/cc/cc.go
+++ b/cc/cc.go
@@ -116,8 +116,6 @@
 	// Used for host bionic
 	LinkerFlagsFile string
 	DynamicLinker   string
-
-	Tools []string
 }
 
 type PathDeps struct {
@@ -160,8 +158,6 @@
 
 	// Path to the dynamic linker binary
 	DynamicLinker android.OptionalPath
-
-	Tools map[string]android.Path
 }
 
 // LocalOrGlobalFlags contains flags that need to have values set globally by the build system or locally by the module
@@ -429,12 +425,6 @@
 	XrefCcFiles() android.Paths
 }
 
-type ToolDependencyTag struct {
-	blueprint.BaseDependencyTag
-
-	Name string
-}
-
 var (
 	dataLibDepTag         = DependencyTag{Name: "data_lib", Library: true, Shared: true}
 	sharedExportDepTag    = DependencyTag{Name: "shared", Library: true, Shared: true, ReexportFlags: true}
@@ -1704,7 +1694,6 @@
 	deps.LateSharedLibs = android.LastUniqueStrings(deps.LateSharedLibs)
 	deps.HeaderLibs = android.LastUniqueStrings(deps.HeaderLibs)
 	deps.RuntimeLibs = android.LastUniqueStrings(deps.RuntimeLibs)
-	deps.Tools = android.LastUniqueStrings(deps.Tools)
 
 	for _, lib := range deps.ReexportSharedLibHeaders {
 		if !inList(lib, deps.SharedLibs) {
@@ -2048,11 +2037,6 @@
 			}, vndkExtDepTag, vndkdep.getVndkExtendsModuleName())
 		}
 	}
-
-	for _, tool := range deps.Tools {
-		actx.AddFarVariationDependencies(ctx.Config().BuildOSTarget.Variations(),
-			ToolDependencyTag{Name: tool}, tool)
-	}
 }
 
 func BeginMutator(ctx android.BottomUpMutatorContext) {
@@ -2235,21 +2219,6 @@
 		depName := ctx.OtherModuleName(dep)
 		depTag := ctx.OtherModuleDependencyTag(dep)
 
-		if toolDep, ok := depTag.(ToolDependencyTag); ok {
-			if toolMod, ok := dep.(android.HostToolProvider); ok {
-				if depPaths.Tools == nil {
-					depPaths.Tools = make(map[string]android.Path)
-				}
-				toolPath := toolMod.HostToolPath()
-				if !toolPath.Valid() {
-					ctx.ModuleErrorf("Failed to find path for host tool %q", toolDep.Name)
-				}
-				depPaths.Tools[toolDep.Name] = toolPath.Path()
-			} else {
-				ctx.ModuleErrorf("Found module, but not host tool for %q", toolDep.Name)
-			}
-		}
-
 		ccDep, ok := dep.(LinkableInterface)
 		if !ok {
 
diff --git a/cc/compiler.go b/cc/compiler.go
index ba14dd5..d5ea2c3 100644
--- a/cc/compiler.go
+++ b/cc/compiler.go
@@ -251,14 +251,6 @@
 		deps.StaticLibs = append(deps.StaticLibs, "libomp")
 	}
 
-	if compiler.hasSrcExt(".y") || compiler.hasSrcExt(".yy") {
-		deps.Tools = append(deps.Tools, "bison", "m4")
-	}
-
-	if compiler.hasSrcExt(".l") || compiler.hasSrcExt(".ll") {
-		deps.Tools = append(deps.Tools, "flex", "m4")
-	}
-
 	return deps
 }
 
@@ -589,7 +581,7 @@
 
 	srcs := append(android.Paths(nil), compiler.srcsBeforeGen...)
 
-	srcs, genDeps := genSources(ctx, srcs, buildFlags, deps.Tools)
+	srcs, genDeps := genSources(ctx, srcs, buildFlags)
 	pathDeps = append(pathDeps, genDeps...)
 
 	compiler.pathDeps = pathDeps
diff --git a/cc/gen.go b/cc/gen.go
index 6f9036b..b0aadc6 100644
--- a/cc/gen.go
+++ b/cc/gen.go
@@ -24,6 +24,7 @@
 )
 
 func init() {
+	pctx.SourcePathVariable("lexCmd", "prebuilts/build-tools/${config.HostPrebuiltTag}/bin/flex")
 	pctx.SourcePathVariable("m4Cmd", "prebuilts/build-tools/${config.HostPrebuiltTag}/bin/m4")
 
 	pctx.HostBinToolVariable("aidlCmd", "aidl-cpp")
@@ -31,6 +32,12 @@
 }
 
 var (
+	lex = pctx.AndroidStaticRule("lex",
+		blueprint.RuleParams{
+			Command:     "M4=$m4Cmd $lexCmd -o$out $in",
+			CommandDeps: []string{"$lexCmd", "$m4Cmd"},
+		})
+
 	sysprop = pctx.AndroidStaticRule("sysprop",
 		blueprint.RuleParams{
 			Command: "$syspropCmd --header-dir=$headerOutDir --public-header-dir=$publicOutDir " +
@@ -59,8 +66,7 @@
 }
 
 func genYacc(ctx android.ModuleContext, rule *android.RuleBuilder, yaccFile android.Path,
-	outFile android.ModuleGenPath, props *YaccProperties,
-	tools map[string]android.Path) (headerFiles android.Paths) {
+	outFile android.ModuleGenPath, props *YaccProperties) (headerFiles android.Paths) {
 
 	outDir := android.PathForModuleGen(ctx, "yacc")
 	headerFile := android.GenPathWithExt(ctx, "yacc", yaccFile, "h")
@@ -91,17 +97,9 @@
 		}
 	}
 
-	bison, ok := tools["bison"]
-	if !ok {
-		ctx.ModuleErrorf("Unable to find bison")
-	}
-	m4, ok := tools["m4"]
-	if !ok {
-		ctx.ModuleErrorf("Unable to find m4")
-	}
-
-	cmd.FlagWithInput("M4=", m4).
-		Tool(bison).
+	cmd.Text("BISON_PKGDATADIR=prebuilts/build-tools/common/bison").
+		FlagWithInput("M4=", ctx.Config().PrebuiltBuildTool(ctx, "m4")).
+		PrebuiltBuildTool(ctx, "bison").
 		Flag("-d").
 		Flags(flags).
 		FlagWithOutput("--defines=", headerFile).
@@ -155,23 +153,13 @@
 	}
 }
 
-func genLex(ctx android.ModuleContext, rule *android.RuleBuilder, lexFile android.Path,
-	outFile android.ModuleGenPath, tools map[string]android.Path) {
-
-	flex, ok := tools["flex"]
-	if !ok {
-		ctx.ModuleErrorf("Unable to find flex")
-	}
-	m4, ok := tools["m4"]
-	if !ok {
-		ctx.ModuleErrorf("Unable to find m4")
-	}
-
-	rule.Command().
-		FlagWithInput("M4=", m4).
-		Tool(flex).
-		FlagWithOutput("-o", outFile).
-		Input(lexFile)
+func genLex(ctx android.ModuleContext, lexFile android.Path, outFile android.ModuleGenPath) {
+	ctx.Build(pctx, android.BuildParams{
+		Rule:        lex,
+		Description: "lex " + lexFile.Rel(),
+		Output:      outFile,
+		Input:       lexFile,
+	})
 }
 
 func genSysprop(ctx android.ModuleContext, syspropFile android.Path) (android.Path, android.Paths) {
@@ -218,22 +206,14 @@
 	return rcFile, headerFile
 }
 
-func genSources(ctx android.ModuleContext, srcFiles android.Paths, buildFlags builderFlags,
-	tools map[string]android.Path) (android.Paths, android.Paths) {
+func genSources(ctx android.ModuleContext, srcFiles android.Paths,
+	buildFlags builderFlags) (android.Paths, android.Paths) {
 
 	var deps android.Paths
 	var rsFiles android.Paths
 
 	var aidlRule *android.RuleBuilder
 
-	var lexRule_ *android.RuleBuilder
-	lexRule := func() *android.RuleBuilder {
-		if lexRule_ == nil {
-			lexRule_ = android.NewRuleBuilder().Sbox(android.PathForModuleGen(ctx, "lex"))
-		}
-		return lexRule_
-	}
-
 	var yaccRule_ *android.RuleBuilder
 	yaccRule := func() *android.RuleBuilder {
 		if yaccRule_ == nil {
@@ -247,19 +227,19 @@
 		case ".y":
 			cFile := android.GenPathWithExt(ctx, "yacc", srcFile, "c")
 			srcFiles[i] = cFile
-			deps = append(deps, genYacc(ctx, yaccRule(), srcFile, cFile, buildFlags.yacc, tools)...)
+			deps = append(deps, genYacc(ctx, yaccRule(), srcFile, cFile, buildFlags.yacc)...)
 		case ".yy":
 			cppFile := android.GenPathWithExt(ctx, "yacc", srcFile, "cpp")
 			srcFiles[i] = cppFile
-			deps = append(deps, genYacc(ctx, yaccRule(), srcFile, cppFile, buildFlags.yacc, tools)...)
+			deps = append(deps, genYacc(ctx, yaccRule(), srcFile, cppFile, buildFlags.yacc)...)
 		case ".l":
 			cFile := android.GenPathWithExt(ctx, "lex", srcFile, "c")
 			srcFiles[i] = cFile
-			genLex(ctx, lexRule(), srcFile, cFile, tools)
+			genLex(ctx, srcFile, cFile)
 		case ".ll":
 			cppFile := android.GenPathWithExt(ctx, "lex", srcFile, "cpp")
 			srcFiles[i] = cppFile
-			genLex(ctx, lexRule(), srcFile, cppFile, tools)
+			genLex(ctx, srcFile, cppFile)
 		case ".proto":
 			ccFile, headerFile := genProto(ctx, srcFile, buildFlags)
 			srcFiles[i] = ccFile
@@ -291,10 +271,6 @@
 		aidlRule.Build(pctx, ctx, "aidl", "gen aidl")
 	}
 
-	if lexRule_ != nil {
-		lexRule_.Build(pctx, ctx, "lex", "gen lex")
-	}
-
 	if yaccRule_ != nil {
 		yaccRule_.Build(pctx, ctx, "yacc", "gen yacc")
 	}